考虑单独计算每个位置的贡献

一个位置i的贡献为c[i]*10^k当且仅当它后面连续(k-1)个数前都没有加号

那么也就是确定了k个位置的情况，剩下的位置未知，用组合数计算即可

注意到当k相同时很多位置的系数是一样的，可以前缀和降低复杂度至O(n)

#pragma GCC opitmize("O3")#pragma G++ opitmize("O3")#include
     
      #include
      
       #include
       
        #define M 1000000007#define LL long long#define N 100010 using namespace std;LL js[N],inv[N],t=1,S=0; char c[N];int n,m,s[N];inline LL C(int n,int m){
      return js[n]*inv[m]%M*inv[n-m]%M; }inline LL pow(LL x,LL k,LL& s){
         for(s=1;k;x=x*x%M,k>>=1) k&1?s=s*x%M:0;}int main(){
         scanf("%d%d%s",&n,&m,c+1);    for(int i=*js=1;i<=n;++i) js[i]=js[i-1]*i%M;    pow(js[n],M-2,inv[n]); for(int i=n;i;--i) inv[i-1]=inv[i]*i%M;    for(int i=1;i<=n;++i) s[i]=s[i-1]+(c[i]-='0');    for(int i=n;i>m;--i,t=t*10%M){
             S=(S+c[i]*C(i-1,m)%M*t%M)%M;        S=(S+s[i-1]*C(i-2,m-1)%M*t%M)%M;    }    printf("%lld\n",S);}