畀定一個以十進制表示嘅整數 $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$ 滿足條件。