经过研究可以发现，每一位的贡献是C(n-2,k-1)+C(n-3,k-1)...C(k-1,k-1)

同时还要注意加号全部在左边的情况。

这里还用了O（n）预处理O(1)组合数的模板。//妙啊。。妙。。。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define LL long long 5  6 using namespace std; 7  8 const int MOD = 1e9+7; 9 const int maxn = 3e5+10;10 11 LL f[maxn],inv[maxn],fac[maxn];12 13 void init()14 {15     fac[0] = fac[1] = inv[0] = inv[1] = f[0] = f[1] = 1;16     for(int i=2;i
        
         =0;i--)49         {50             ans += (s[i]-'0')*(save[N-1-i]+C(i,K)*base%MOD)%MOD;51             ans %= MOD;52             base = base*10%MOD;53         }54         printf("%I64d\n",ans);55     }56 }