问题背景

闵老师和李老师的工资差距很大！而在古老的魔法阵中，数字被视为能量的载体。每个n位数字对应一个魔法序列，需满足特定条件才能激活魔法。你的任务是统计在给定区间内符合所有魔法条件的数字数量。 激活魔法就可以给闵老师加工资！

问题描述

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

• $x$的各位数字之和等于$a$；
• $x$中任意相邻两位数字的差的绝对值不超过$b$；
• $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