406602: GYM102452 J Junior Mathematician

Number theory is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of objects made out of integers or defined as generalizations of the integers.

Portrait of Carl Friedrich Gauss by C.A. Jensen. Public Domain.

Chandra is a junior mathematician who has just guaduated from university and she specializes in number theory. It has always been her ambition to become as famous a mathematician as Gauss. In her recent work, she invented a new function $$$f(x)$$$ for a postive integer $$$x$$$ during her recent research in number theory. Let $$$k$$$ be the number of digits in the decimal representation of $$$x$$$, and $$$d(x,i) \ (1 \le i \le k)$$$ be the $$$i$$$-th digit of $$$x$$$ in its decimal representation. Then $$$$$$f(x)=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} d(x,i) \cdot d(x,j)$$$$$$

Chandra has also found a mysterious integer $$$m$$$. She thinks that positive integers which satisfy the property $$$x \equiv f(x) \pmod{m}$$$ may be very important for her research. She wants to find out the number of such integers $$$x$$$ which also satisfy $$$L \le x \le R$$$. She only needs to know that number modulo $$$10^9+7$$$, which is another mysterious integer she has found during her research. Unfortunately, the numbers $$$L$$$ and $$$R$$$ can be very large and it is not feasible to solve that problem by hand, even for a mathematician. In order to publish her paper and become a well-known mathematician, Chandra asks you, a famous programmer, to help her overcome this obstacle in her research.

The input contains multiple cases. The first line of the input contains a single positive integer $$$T$$$, the number of cases.

For each case, the first line and the second line of the input each contains a single integer, $$$L$$$ and $$$R \ (10 \le L \le R < 10^{5\,000})$$$, respectively. The third line of the input contains a single integer $$$m \ (2 \le m \le 60)$$$.

It is guaranteed that the sum of the number of digits of $$$R$$$ over all cases doesn't exceed $$$5\,000$$$.

For each case, print a single integer on a single line, the number of integers $$$x$$$ satisfying the required conditions, modulo $$$10^9+7$$$.

2
10
50
17
33
33
3

2
1