十進法で表された整数 $N$ が与えられます。
$N$ の各桁の数字を並び替えることで作ることができ、かつ先頭に余分なゼロ(leading zeros)を含まないすべての整数を考えます。
そのような整数のうち $11$ で割り切れるものの個数を、素数である $2147483647$ ($= 2^{31} - 1$) で割った余りを求めてください。
なお、$N$ の各桁の数字を並び替えて作られる整数には $N$ 自身も含まれることに注意してください。
入力
入力は以下の形式で与えられます:
$$N$$
- 入力される値はすべて整数である。
- $1 \le N < 10^{2 \times 10^6}$
- $N$ は先頭に余分なゼロを含まない十進表記で与えられる。
出力
答えを $1$ 行で出力してください。
入出力例
入力例 1
1001
出力例 1
2
入力例 2
31415926535
出力例 2
144000
注記
$1$ 番目の例では、$1100$ と $1001$ が条件を満たします。