Horse Races （数位dp）

Horse Races （数位dp）

Petya likes horse racing very much. Horses numbered from l to r take part in the races. Petya wants to evaluate the probability of victory; for some reason, to do that he needs to know the amount of nearly lucky horses' numbers. A nearly lucky number is an integer number that has at least two lucky digits the distance between which does not exceed k. Petya learned from some of his mates from Lviv that lucky digits are digits 4 and 7. The distance between the digits is the absolute difference between their positions in the number of a horse. For example, if k = 2, then numbers 412395497, 404, 4070400000070004007 are nearly lucky and numbers 4, 4123954997, 4007000040070004007

Petya prepared t intervals [li, ri] and invented number k, common for all of them. Your task is to find how many nearly happy numbers there are in each of these segments. Since the answers can be quite large, output them modulo 1000000007 (109 + 7).

Input

The first line contains two integers t and k (1 ≤ t, k ≤ 1000) — the number of segments and the distance between the numbers correspondingly. Next t lines contain pairs of integers li and ri (1 ≤ l ≤ r ≤ 101000). All numbers are given without the leading zeroes. Numbers in each line are separated by exactly one space character.

Output

Output t lines. In each line print one integer — the answer for the corresponding segment modulo 1000000007 (109 + 7).

Example

Input

1 2 1 100

Output

4

Input

1 2 70 77

Output

2

Input

2 1 1 20 80 100

Output

0 0

题目大概：

找出给定区间内，4和7  或  4和4  或7和7  间隔小于k的数字的个数。

思路：

因为是只要存在便可，没要求数量，所以一般只需判断一次即可，以后遇到4和7，还是直接当什么也每遇到即可。

但是这个数据量大，用字符串输入，最后还要判断最小的数是不是符合条件，符合的话，要加上。

代码：

#include #include #include using namespace std;int mod=1000000007;int dp[1005][2010];int a[1005];int k;int sove(int pos,int ju,int limit){ if(pos==-1)return ju==0; if(!limit&&dp[pos][ju]!=-1)return dp[pos][ju]; int end=limit?a[pos]:9; int ans=0; for(int i=0;i<=end;i++) { int nju=(ju==0?0:ju+1); if(i==4||i==7) { if(ju<=k)nju=0; else nju=1; } ans=(ans+sove(pos-1,nju,limit&&i==end))%mod; } if(!limit)dp[pos][ju]=ans; return ans;}int go(char s[]){ int pos=0; int l=strlen(s); for(int i=l-1;i>=0;i--) { a[pos++]=s[i]-'0'; } return sove(pos-1,k+2,1);}int check(char s[]){ int ju=k+1; for(int i=0;s[i];i++) { if(ju==0)break; if(s[i]=='4'||s[i]=='7') { if(ju<=k)ju=0; else ju=1; } else ju++; } return ju==0;}int main(){ int t; scanf("%d%d",&t,&k); char s1[1005],s2[1005]; memset(dp,-1,sizeof(dp)); while(t--) { scanf("%s%s",s1,s2); int b=go(s2); int a=go(s1); if(check(s1))a--; b=((b-a)%mod+mod)%mod; printf("%d\n",b); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。