光棍

题目描述:

 快要到七夕了,又到了交(nue)往(gou)的季节。

        恶梦坐在教室里,作为一个纯屌丝的他当然不会关心要送什么礼物给女生,然而他的前桌yves却在忙碌着各种各样的的短信。

        恶梦注意到yves发短信给的电话号码似乎都满足着特别的性质,难道yves的"好朋友"是满足正态分布的？

        由于yves有着自己最喜欢的数字a,2 <= a <= 9

        恶梦从这里入手,发现了一些端倪。

        假设yves发的电话号码是一个十进制数字S

        恶梦发现S会满足以下三个性质中的一个

1. S是a的倍数。
2. S在十进制表示下的各项数字加起来是a的倍数。
3. S的某一位是a

        比如说当a = 7时,21,16,17这三个数字都是会被yves发短信的,他们分别满足1,2,3性质。

        恶梦很担心所有的女同学都被yves抢走了,但他一下子又数不过来那些同学没有被yves抢走,所以他把这个问题交给了你。

        他会给你两个自然数L,R,以及yves最喜欢的数字a,

        他并不希望你告诉他在[L,R]中有多少个同学没有被抢走,而希望你告诉他这些数字的平方和。

        比如说3,7是合法的,那么你应该输出3^2 + 7^2 = 58这个数。

        当然,由于答案可能很大,你只需要将答案对10^9 + 7取模即可。

输入格式:

输入的第一行包括一个正整数T,表示总共有T组询问。

接下来有T行,每行三个整数L,R,A。

输出格式:

输出包括T行,每行一个整数,表示对10^9 + 7取模的答案。

样例输入:

3
2 20 6
3 203 7
11 771 2

样例输出:

1884
1593269
32817226

提示:

 对于15%的数据,0 <= L <= R <= 10^6,T = 1

对于35%的数据,0 <= L <= R <= 10^7,T = 1

另外有25%的数据,A = 2,L = 10^k,R = 10^v,k和v都是自然数。

 对于100%的数据,0 <= L <= R <= 10^18,2 <= A <= 9, T <= 100

时间限制: 1000ms
空间限制: 256MB

---