问题 E: Educational Problem I

You are given n, m, l, r. Count the number of integer sequence a1, a2, . . . , an satisfying the following conditions, modulo 998 244 353: • ∀i ∈ Z ∩ [1, n], l ≤ ai ≤ r. • S1( Pn i=1 ai) ≡ S2( Pn i=1 ai) (mod m). Here S1(x) denotes the sum of the digits of x in decimal notation, and S2(x) denotes the sum of the square of digits of x in decimal notation. For example, S1(123) = 1 + 2 + 3 = 6, S2(123) = 12 + 22 + 32 = 14.

The only line contains four integers n, m, l, r (1 ≤ n, m ≤ 20, 0 ≤ l ≤ r < 101000). 

Output an integer representing the answer. 

3 5 2 5

26