问题背景

在古老的魔法阵中，数字被视为能量的载体。每个n位数字对应一个魔法序列，需满足特定条件才能激活魔法。你的任务是统计在给定区间内符合所有魔法条件的数字数量。

问题描述

给定两个n位数L和R（可能有前导零，n≤18），以及三个整数a、b、k。要求统计在区间[L, R]内满足以下条件的数字x的个数：

1. 数字和条件：x的各位数字之和等于a；
2. 相邻差条件：x中任意相邻两位数字的差的绝对值不超过b；
3. 关键位条件：x的最左边的非零数字位于第k位（从左数起，k≤n）。

具体说明：

• 若k=1，则x的最高位（第1位）不能为0；
• 若k>1，则x的前k-1位必须全为0，且第k位不能为0；
• 若不存在符合条件的x（如k>n或条件矛盾），输出0。

输入格式

第一行输入两个整数n和T（n≤18，T≤10），表示数字的位数和询问次数。 第二行输入两个n位字符串L和R（表示数值范围，可能有前导零）。 第三行输入三个整数a、b、k（a≥0，b≥0，1≤k≤n）。

输出格式

对于每个询问，输出符合条件的数字个数，结果对1e9+7取模。

样例输入

3 1  
000 222  
3 2 2  

样例输出

2

样例解释

符合条件的数字需满足：

• 前1位为0（k=2），第2位非零；
• 各位和为3；
• 相邻位差的绝对值≤2。

可能的数字：

• 012：0+1+2=3，相邻差|0-1|=1≤2，|1-2|=1≤2 → 有效；
• 021：0+2+1=3，相邻差|0-2|=2≤2，|2-1|=1≤2 → 有效；
• 其他如030（和为3但|0-3|=3>2）、011（和为2）均无效。故总共有2个。