D. 完蛋!我被数字包围了

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

某个同学在CCPC深圳站比赛期间被学长胁迫,自掏腰包买了《完蛋!我被美女包围了!》这款游戏并且玩得不亦乐乎,学长趁着他对屏幕姨母笑的时候拍照发到了群里。 你说的对,但是《完蛋!我被美女包围了!》是一款模拟恋爱的全动态真人互动影像作品。你将以第一人称与十位性格各异、长相各异的美女相识、相知、相爱,展开一段又一段沉浸式甜蜜之旅。

这个同学恼羞成怒之余,自己设计了一款《完蛋!我被数字包围了!》

现在有 个数字和他们的分身(也就是说可以有多个相同数字)站在了他的面前为他争风吃醋, 个数字组成了一个字符串 ,现在他可以自由调动 中数字的顺序,如果能使最终由数组经过特定方式:

对于数字排列

转换成的十进制数 是一个正整数的平方,那么就可以做到所有数字都不会掉好感度,否则数字们就会因为吃醋而掉好感度。

现在他想知道一共有几种排列方式可以使数字们不会掉好感度(数字的分身们交换位置算同一种方案,如由 三个数字组成的平方数 只会被计算为一种方案,两个 不分先后)

输入格式

第一行一个正整数 ,代表数字的个数。 第二行一个字符串 ,代表争风吃醋的数字们。

输出格式

一行,输出让数字们不会掉好感度的排列方案数。

样例

样例输入1:

4
4320

样例输出1:

2

样例输入2:

3
010

样例输出2:

2

样例输入3:

13
8694027811503

样例输出3:

840

数据范围与提示

样例解释 1

考虑

考虑

数据范围

对于所有数据,满足:

  • 保证由数字组成。

  • 是整数。