Summits on the Odometer

Time limit: 4000 msMemory limit: 64 MB

An observatory displays each positive integer as a row of decimal digits. Consecutive equal digits form a plateau.

More precisely, compress every maximal contiguous group of equal digits in the usual decimal representation of an integer $X$ into one digit. Let the resulting plateau sequence be

$p_1, p_2, \ldots, p_T.$

A plateau $p_i$ is a summit if

$1 < i < T, \qquad p_i > p_{i-1}, \qquad p_i > p_{i+1}.$

Thus, the first and last plateaus are never summits.

The digit sum of $X$ , denoted by $\operatorname{ds}(X)$ , is the sum of all digits in its usual decimal representation, including repeated digits inside a plateau.

Given an interval $[L,R]$ and integers $K$ , $M$ , and $S$ , count the integers $X$ in the interval that satisfy both conditions:

the plateau sequence of $X$ contains exactly $K$ summits;
$\operatorname{ds}(X) \bmod M = S$ .

Because the count can be large, report it modulo $998244353$ .

Input

The first line contains the decimal representation of $L$ .

The second line contains the decimal representation of $R$ .

The third line contains three integers $K$ , $M$ , and $S$ .

The constraints are:

$1 \le L \le R < 10^{200}$ ;

Output

Print the number of integers $X$ in the interval $[L,R]$ that have exactly $K$ summit plateaus and satisfy the required digit-sum congruence. Print the answer modulo $998244353$ .

Samples

Sample 1

Input

1
150
1 3 0

Output

The qualifying integers are $120$ , $132$ , $141$ , and $150$ .

Sample 2

Input

1210
1222
1 7 6

Output

The qualifying integers are $1212$ , $1219$ , and . In , the plateau containing the two equal digits is a summit.

Summits on the Odometer

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions