C. Add One--Divide by Zero 2021 and Codeforces Round #714 (Div. 2)

Divide by Zero 2021 and Codeforces Round #714 (Div. 2)

C. Add One

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer nn. You have to apply mm operations to it.

In a single operation, you must replace every digit dd of the number with the decimal representation of integer d+1d+1. For example, 19121912 becomes 2102321023 after applying the operation once.

You have to find the length of nn after applying mm operations. Since the answer can be very large, print it modulo 109+7109+7.

Input

The first line contains a single integer tt (1≤t≤2⋅1051≤t≤2⋅105) — the number of test cases.

The only line of each test case contains two integers nn (1≤n≤1091≤n≤109) and mm (1≤m≤2⋅1051≤m≤2⋅105) — the initial number and the number of operations.

Output

For each test case output the length of the resulting number modulo 109+7109+7.

Example

input

Copy

5
1912 1
5 6
999 1
88 2
12 100

output

Copy

5
2
6
4
2115

Note

For the first test, 19121912 becomes 2102321023 after 11 operation which is of length 55.

For the second test, 55 becomes 2121 after 66 operations which is of length 22.

For the third test, 999999 becomes 101010101010 after 11 operation which is of length 66.

For the fourth test, 8888 becomes 10101010 after 22 operations which is of length 44.

=========================================================================

对于每一个数字其操作固定操作次数带来的效果也是固定的，故我们可以预处理出每种数字操作m次的长度。 dp[i][j]代表操作i次，j数字获得的长度， 一般的0-8，操作i次获得的长度是j+1，操作i-1次获得的长度，而对于9来说，是i-1次，获得0,1长度的总和。

 
# include<iostream>
# define mod 1000000007
using namespace std;
 
typedef long long int ll;
 
ll dp[200000+10][10];
 
int main ()
{
 
  for(int i=0;i<=9;i++)
  {
      dp[0][i]=1;
  }
  for(int i=1;i<=200000;i++)
  {
      for(int j=0;j<9;j++)
      {
 
         dp[i][j]=dp[i-1][j+1];
 
      }
 
      dp[i][9]=(dp[i-1][0]+dp[i-1][1])%mod;
 
 
  }
 
  int t;
 
  cin>>t;
  while(t--)
  {
 
     ll n,m;
     
     scanf("%lld%lld",&n,&m);
     
     
      while(n)
      {
          ans=(ans+dp[m][n%10])%mod;
 
          n/=10;
      }
 
      cout<<ans<<'\n';
 
  }
    return 0;
 
}