“根本赢不了，我听不懂。”
“是啊，从什么时候起我也变得不再相信命运了。一定要赢啊，以人类的身份。”
“没问题吧，你一定要赢啊，迪迦奥特曼。”
大古变身成为迪迦奥特曼，与加坦杰厄展开决战。然而加坦杰厄的超强防御力让迪迦奥特曼束手无策。最终迪迦奥特曼被夺走了光，再次变成了石像，沉入海底。众人制定了营救计划，想用光遗传因子转换器让迪迦奥特曼复苏。然而行动中被加坦杰厄发现，营救计划以失败告终。
”其实每一个人，都能靠自己的力量变成光的。“
正当大家绝望之际，世界各地仍相信迪迦的孩子们变成了一道道光，让迪迦成功复活，并变成闪耀迪迦，击败了加坦杰厄。
那一刻，我们都变成了光，成为了光能量的一份子。但在这些光芒里，包含着来自大自然的生息，包括着动物，植物，人类。迪迦想知道，在这些光芒里，有哪些是地球村的人给予的光芒。
每一个光芒都有着他自己的光能量值 $X$ $(X≥1)$ ,已知 $X$ 的数字长度为 $len$ ,则 $X_i$ 为该数字从左往右数第 $i$ 位,$(1≤i≤len)$ 。来自人类的光芒，其光芒值有着独特的秘密，令 $sum=\sum_{i=1}^{len-1}\sum_{j=i+1}^{len}X_i*X_j$, 那么满足 $sum\equiv X \pmod{m}$ 的便是人类的光芒。
现在迪迦在收集光芒中，迪迦想知道在这些光芒堆里，满足光芒值 $L≤X≤R$ 当中有多少是人类的光芒。由于答案可能会很大，请将答案$mod$ $1000000007$后输出。
第一行给出测试样例数 $T$ ,表示共有 $T$ 组测试样例。($1≤T≤20$)
接下来对于每一组样例：
第一行给出左区间边界 $L$
第二行给出右区间边界 $R$ ,其中 $(1≤L≤R≤10^{5000})$,输入保证没有前导0
第三行给出整数 $m$,表示为上文的 $mod$ 值, $(2≤m≤60)$
对于每组测试样例,输出 $[L,R]$ 共有多少个光芒值是来自人类的，答案 $mod$ $1000000007$
给定一个正整数 $m$ ，如果两个整数 $a$ 和 $b$ 满足 $a-b$ 能够被 $m$ 整除，即 $\frac{a-b}{m}$得到一个整数，那么就称整数 $a$ 与 $b$ 对模 $m$ 同余，记作 $a≡b$ ( $mod$ $m)$。