#include #include #include using namespace std; long long mod=1000000007; char str[210000]; char A[210000]; char B[210000]; int P; int m3[110000]; int y[110000]; int cnt[2][3]; int lim=1000; long long dp[210000][3][2][3]; int las=0; char tmp[10]; long long count(int t){ for(int i=0;i<210000;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++) dp[i][j][k][l]=0; for(int i=1;i<10;i++){ dp[1][i%3][i==3][(i==(str[0]-'0'))?0:((i>(str[0]-'0'))?2:1)]++; } int len=strlen(str); for(int i=1;istr[i]-'0')tl=2; } dp[i+1][tj][tk][tl]=(dp[i+1][tj][tk][tl]+dp[i][j][k][l])%mod; } } } long long ret=0; if(len>las){ for(int i=len-las;i10){lim*=10;las++;} if(P>100){lim*=10;las++;} for(int i=0;i