AT_abc324_d [ABC324D] Square Permutation

[problemUrl]: https://atcoder.jp/contests/abc324/tasks/abc324_d 数字のみからなる、長さ $ N $ の文字列 $ S $ が与えられます。 $ S $ を並べ替えてできる文字列を十進法の整数として解釈したもののうち、平方数であるようなものがいくつあるか求めてください。 より厳密には、次のようになります。 $ S $ の先頭から $ i $ 番目 $ (1\leq\ i\leq\ N) $ の数字に対応する数を $ s\ _\ i $ とします。 $ (1,\ \ldots,\ N) $ の順列 $ P=(p\ _\ 1,p\ _\ 2,\ldots,p\ _\ N) $ によって $ \displaystyle\ \sum\ _\ {i=1}\ ^\ N\ s\ _\ {p\ _\ i}10\ ^\ {N-i} $ と書ける整数のうち、平方数であるようなものがいくつあるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

答えを $ 1 $ 行で出力せよ。

### 制約 - $ 1\leq\ N\leq\ 13 $ - $ S $ は数字のみからなる長さ $ N $ の文字列 - $ N $ は整数 ### Sample Explanation 1 $ P=(4,2,3,1) $ とすると、$ s\ _\ 4\times10\ ^\ 3+s\ _\ 2\times10\ ^\ 2+s\ _\ 3\times10\ ^\ 1+s\ _\ 1=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 $ を出力してください。 ### Sample Explanation 2 $ P=(1,3,2) $ もしくは $ P=(3,1,2) $ とすると、$ \displaystyle\sum\ _\ {i=1}\ ^\ Ns\ _\ {p\ _\ i}10\ ^\ {N-i}=1=1\ ^\ 2 $ となります。 $ P=(2,1,3) $ もしくは $ P=(2,3,1) $ とすると、$ \displaystyle\sum\ _\ {i=1}\ ^\ Ns\ _\ {p\ _\ i}10\ ^\ {N-i}=100=10\ ^\ 2 $ となります。 これら以外の並べ替え方では平方数にならないため、$ 2 $ を出力してください。 異なる並べ替え方でも、並べ替えた結果の数が同じなら $ 1 $ つと数えることに注意してください。