给你一个用十进制表示的整数 $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 满足条件。