問題文

十進法で表された整数 N が与えられます。

N の各桁を先頭の桁が 0 にならないように並べ替えてできる整数のうち、11 の倍数であるものの個数を素数 2147483647\ (= 2^{31}-1) で割った余りを求めてください。

なお、N の各桁を並べ替えてできる整数には N 自身も含みます。

制約

• 入力は全て整数
• 1\leq N < 10^{2 \times 10^6}
• N は先頭の桁が 0 でない十進表現で与えられる

入力例 1

1001

出力例 1

2

1100 と 1001 が条件を満たします。

入力例 2

31415926535

出力例 2

144000