“根本赢不了，我听不懂。”
“是啊，从什么时候起我也变得不再相信命运了。一定要赢啊，以人类的身份。”
“没问题吧，你一定要赢啊，迪迦奥特曼。”
大古变身成为迪迦奥特曼，与加坦杰厄展开决战。然而加坦杰厄的超强防御力让迪迦奥特曼束手无策。最终迪迦奥特曼被夺走了光，再次变成了石像，沉入海底。众人制定了营救计划，想用光遗传因子转换器让迪迦奥特曼复苏。然而行动中被加坦杰厄发现，营救计划以失败告终。
”其实每一个人，都能靠自己的力量变成光的。“
正当大家绝望之际，世界各地仍相信迪迦的孩子们变成了一道道光，让迪迦成功复活，并变成闪耀迪迦，击败了加坦杰厄。
那一刻，我们都变成了光，成为了光能量的一份子。但在这些光芒里，包含着来自大自然的生息，包括着动物，植物，人类。迪迦想知道，在这些光芒里，有哪些是地球村的人给予的光芒。
每一个光芒都有着他自己的光能量值 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)。