Digit Division

Time limit: 1 s Memory limit: 512 MiB

We are given a sequence of n decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer m.

Find the number of different such partitions modulo 109 + 7. When determining if two partitions are different, we only consider the locations of subsequence boundaries rather than the digits themselves, e.g. partitions 2|22 and 22|2 are considered different.

Input

The first line contains two integers n and m (1 ≤ n ≤ 300 000, 1 ≤ m ≤ 1 000 000) – the length of the sequence and the divisor respectively. The second line contains a string consisting of exactly n digits.

Output

Output a single integer – the number of different partitions modulo 109 + 7.

Example

input

4 2

1246

output

input

4 7

2015

output

//题意: n 位长的十进制数字，在其中可以任意插入分割线，分割后，要使每一段不为空，并且可以整除 m ，合法分割的方案数

//题目是极其简单的，如果前一部分可以整除 m ，那么，这部分乘10的x次方后依然可以整除，然后算出所有可分割的位置后

C(0,all),C(1,all)+...+C(all,all); 这些必然合法

= 2^^all

但是，此题如果没想清楚，写代码会进坑，此题是对方案数取模，all 是%m==0的方案数，进了坑半天想不出来，唉，还是太菜啊，一度wa在第三组，真是日狗了

 # include <cstdio>

 # include <cstring>

 # include <cstdlib>

 # include <iostream>

 # include <vector>

 # include <queue>

 # include <stack>

 # include <map>

 # include <bitset>

 # include <sstream>

 # include <set>

 # include <cmath>

 # include <algorithm>

 # pragma  comment(linker,"/STACK:102400000,102400000")

 using namespace std;

 # define LL          long long

 # define pr          pair

 # define mkp         make_pair

 # define lowbit(x)   ((x)&(-x))

 # define PI          acos(-1.0)

 # define INF         0x3f3f3f3f

 # define eps         1e-

 # define MOD         

 inline int scan() {

     int x=,f=; char ch=getchar();

     while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 inline void Out(int a) {

     if(a<) {putchar('-'); a=-a;}

     if(a>=) Out(a/);

     putchar(a%+'');

 }

 # define MX

 /**************************/

 char num[MX];

 LL qk_mi(LL base,LL x)

 {

     LL res = ;

     while (x)

     {

         if (x%==) res = (res*base)%MOD;

         base=base*base%MOD;

         x/=;

     }

     return res;

 }

 int main()

 {

     int n,m;

     while (scanf("%d%d",&n,&m)!=EOF)

     {

         scanf("%s",num);

         LL zuo = ;

         LL all = ;

         for (int i=;i<n;i++)

         {

             zuo=(zuo*+(num[i]-''))%m;

             if (zuo%m==) all++;

         }

         all--;

         if (zuo%m!=)

             printf("0\n");

         else

         {

             LL ans = qk_mi(,all);

             printf("%lld\n",ans);

         }

     }

     return ;

 }

巴特西

Digit Division

最新文章

热门文章