Migrated from Lutece 3144 虾头卷狗莫得情感

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

虾头卷狗王 L&* 行刑前说：“想要我的宝藏吗，去找吧，我把所有学习资料都藏在那里了。” 从此开启大虾卷时代。 前面忘了，中间忘了，探险家诚哥终于找到了宝藏所在的地方，然而入口大门上存在数个密码锁，这对于熟悉密码学的诚哥来说毫无压力，在破译所有的密码并成功进入后，虾头卷狗王的幻影浮现在宝藏上空：“恭喜你找到了我的宝藏，但我现在还要给你来个考验，看看你是不是真正合格的虾头卷狗。” 虾卷王的终极考验如下： 给定两个数 $A$ 和 $B$ ，求 $[A,B]$ 中总共有多少个数满足不同位数的个数等于 $X$ 。 现在请你帮助诚哥在规定时间内完成考验，得到学习资料。由于故事的时代背景，计数采用 $Y$ 进制，但你只需要告诉诚哥十进制答案即可。

数不同位数的个数指的是将这个数字每个位上的数去重并统计数量。 如123含有1,2,3，个数为3；114514含有1,4,5，个数为3；99999只有9，个数为1。

Input

第一行两个正整数 $T,Y$ 表示总询问次数和采用的进制数。 对每次询问存在四行输入， 第一行输入正整数 $N$ ，表示 $A,B$ 的位数长度。 接下来两行分别输入$A$ 和 $B$ 。 最后一行输入一个整数 $X$ 。

Output

对每次询问输出一个整数，即满足条件的答案数对 $10^9+7$ 的模。

Samples

1 10
2
40
59
2

18

1 16
2
40
7F
2

60

Constraints

$1 \le T \le 10,1\le N \le 20000,1\le X \le 9,3\le Y \le 16.$ 保证 $A$ 和 $B$ 都没有前导零且正好 $N$ 位。

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming