题目描述

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

求将 $S$ 重新排列以后，可以得到多少个 不同的完全平方数。

例如字符串 144 的所有排列中，只能得到一个 $144$ 这个完全平方数。重复得到相同的数字只计算一次。

输入格式

第一行输入一个整数 $N$

第二行输入一个字符串 $S$

输出格式

输出一个整数代表方案数

4
4320

2

3
010

2

13
8694027811503

840

样例 1 解释

若按照 $P=(4,2,3,1)$ 的顺序排列字符串，我们有 $0\times10 ^ 3+3\times10 ^ 2+2\times10 ^ 1+4=324=18 ^ 2$ 。 若按照 $P=(3,2,4,1)$ 的顺序排列, 我们有 $s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2$ 。

没有其他排列组合产生平方数，因此应该打印 $2$ 。

提示

对于 $60\%$ 的数据满足， $1\leq |S|\leq 10$，其中 $|S|$ 为字符串的长度。

对于 $100\%$ 的数据满足， $1\leq |S|\leq 13$，其中 $|S|$ 为字符串的长度。