Count the number of integer sequence a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an satisfying the following conditions, modulo 998244353998\,244\,353998244353:
S1(∑i=1nai)≡S2(∑i=1nai)(modm)S_1(\sum_{i=1}^{n} a_i) \equiv S_2(\sum_{i=1}^{n} a_i) \pmod{m}S1(∑i=1nai)≡S2(∑i=1nai)(modm). Here S1(x)S_1(x)S1(x) denotes the sum of the digits of xxx in decimal notation, and S2(x)S_2(x)S2(x) denotes the sum of the square of digits of xxx in decimal notation. For example, S1(123)=1+2+3=6S_1(123) = 1+2+3=6S1(123)=1+2+3=6, S2(123)=12+22+32=14S_2(123)=1^2+2^2+3^2=14S2(123)=12+22+32=14.
输入格式
The only line contains four integers n,m,l,rn,m,l,rn,m,l,r (1≤n,m≤201 \leq n, m \leq 201≤n,m≤20, 0≤l≤r<1010000 \leq l \leq r < 10^{1000}0≤l≤r<101000).