平方排列

题目描述

给定一个长度为 $N$、由数字组成的字符串 $S$。

求出将 $S$ 的某个排列解释为一个十进制整数后，能够得到的平方数的个数。

更正式地，解决以下问题。

设 $s _ i$ 为 $S$ 从开头数第 $i$ 个数字（$1\leq i\leq N$）所对应的数。

求能用排列 $P=(p _ 1,p _ 2,\ldots,p _ N)$（$(1, \dots, N)$ 的一个排列）表示为 $\displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i}$ 的平方数的个数。

输入格式

输入按以下格式从标准输入给出：

$N$
$S$

输出格式

在一行中输出答案。

样例

4
4320

2

对于 $P=(4,2,3,1)$，有 $s _ 4\times 10 ^ 3+s _ 2\times 10 ^ 2+s _ 3\times 10 ^ 1+s _ 1=324=18 ^ 2$。

对于 $P=(3,2,4,1)$，有 $s _ 3\times 10 ^ 3+s _ 2\times 10 ^ 2+s _ 4\times 10 ^ 1+s _ 1=2304=48 ^ 2$。

其他排列都不能得到平方数，所以输出 $2$。

3
010

2

对于 $P=(1,3,2)$ 或 $P=(3,1,2)$，有 $\displaystyle\sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i}=1=1 ^ 2$。

对于 $P=(2,1,3)$ 或 $P=(2,3,1)$，有 $\displaystyle\sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i}=100=10 ^ 2$。

其他排列都不能得到平方数，所以输出 $2$。 注意，如果不同的排列得到相同的数，则不把它们区分开。

13
8694027811503

840

数据范围

• $1\leq N\leq 13$
• $S$ 是长度为 $N$、由数字组成的字符串。
• $N$ 是整数。