給定一個以十進位表示的整數 $N$。
考慮所有可以透過重新排列 $N$ 的數位而形成、且不含前導零的整數。
求這些整數中能被 $11$ 整除的個數,結果對質數 $2147483647$($= 2^{31} - 1$)取模。
請注意,透過重新排列 $N$ 的數位所形成的整數包含 $N$ 本身。
輸入格式
輸入以以下格式給出:
$$N$$
- 所有輸入值皆為整數。
- $1 \le N < 10^{2 \times 10^6}$
- $N$ 以十進位給出,且不含前導零。
輸出格式
在單獨一行輸出答案。
範例
輸入格式 1
1001
輸出格式 1
2
輸入格式 2
31415926535
輸出格式 2
144000
說明
在第一個範例中,$1100$ 與 $1001$ 滿足條件。