Monotone Digit Sum Vectors

Little S loves counting. One night, while counting numbers before sleep, she reached the number 977431 and decided to sleep. However, she noticed that the digits of that number were in monotone non‐increasing order (i.e. every digit is not less than the digit to its right). Fascinated by this observation, she wondered about the following problem:

Given three integers \(L\), \(R\) and \(k\), count the number of \(k\)-dimensional vectors \((a_1, a_2, \dots, a_k)\) such that for each \(i\), \(L \le a_i \le R\), and the sum \(S = a_1+a_2+\cdots+a_k\) has its decimal digits in monotone non-increasing order; that is, if \(S\) is written in base 10 as \(d_1d_2\cdots d_m\), then \[ d_1 \ge d_2 \ge \cdots \ge d_m. \] Since the answer may be very large, output it modulo 998244353.

Note: A single digit number is always considered to have its (only) digit in monotone non-increasing order.

inputFormat

The input consists of a single line containing three integers \(L\), \(R\) and \(k\) separated by spaces.

\(L, R\) define the inclusive range of each component of the vector, and \(k\) is the dimension of the vector.

outputFormat

Output a single integer, the number of \(k\)-dimensional vectors satisfying the conditions, modulo 998244353.

sample

1 5 2

25