AT_utpc2025_d Divisible by 11

十進法で表された整数 $ N $ が与えられます。 $ N $ の各桁を先頭の桁が `0` にならないように並べ替えてできる整数のうち、 $ 11 $ の倍数であるものの個数を素数 $ 2147483647\ (= 2^{31}-1) $ で割った余りを求めてください。 なお、 $ N $ の各桁を並べ替えてできる整数には $ N $ 自身も含みます。

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

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

### Sample Explanation 1 $ 1100 $ と $ 1001 $ が条件を満たします。 ### Constraints - 入力は全て整数 - $ 1\leq N < 10^{2 \times 10^6} $ - $ N $ は先頭の桁が `0` でない十進表現で与えられる