#P18004. Divisible by 11

Divisible by 11

Divisible by 11

给定一个以十进制表示的正整数 NN。

考虑重新排列 NN 的全部数位所能得到的所有没有前导零的整数。求其中能被 1111 整除的不同整数个数,答案对质数 2147483647=231−12147483647=2^{31}-1 取模。

相同数位不可区分;原来的整数 NN 本身也包含在考虑范围内。

输入格式

一行,包含正整数 NN 的十进制表示,不含前导零。

输出格式

输出答案对 21474836472147483647 取模的结果。

数据范围

1≤N<102×1061\le N<10^{2\times10^6},即十进制位数不超过 2×1062\times10^6。

样例 1

输入

1001

输出

2

样例 2

输入

31415926535

输出

144000