昨天ZZD大神邀请我做一道题，说这题很有趣啊。
哇，然后我被虐了。
Orz ZZD
题目大意：
你有一个长度为n的'0-9'串，你要在其中加入k个'+'号，每种方案就会形成一个算式，算式算出来的值记做这次方案的贡献。
问：所有方案的贡献，对1e9+7取模。
n,k<=1e5.
首先我和zzd先探讨了一会儿暴力一点的做法，唔，非常好弄的是k*n^2，枚举子串，考虑这个子串出现在了多少个方案中，然后就是枚举左边多少个'+'，然后一堆组合数...啪啦啪啦...
然后觉得既然两边分的'+'号加起来的总和相等，是不是可以不用枚举呢，比如一个预处理什么的...啪啦啪啦...
好啦，感觉上面的研究不下去了...
然后又想，不是要O(n)么，感觉像是对每个字符考虑，考虑它作为个位、十位、百位...等等的贡献。
怎么算呢？似乎现在状态比刚才好一点了？...
首先是i作为这一段的开头，j作为这一段的结尾。
现在是i作为这一段的第j位...好啦...然后我还是想不到= =
ZZD就开始秒题啦...因为原题相当于在n-1的空隙中放k个隔板。
那么若i不在最后一段，那么我先强制在i+j后插一个隔板[保证i是第j位]，并且强制i到i+j之间的j-1个位置不能放，同时i+j后的位置已经放了，所以还剩n-j-1个位置，k-1个隔板，即C(n-j-1,k-1)种方案。
若i在最后一段，那么我强制i到n的j-1个位置不能放，就是C(n-j,k)种方案。
好啊，发现这个东西居然和i都没有关系，那我是不是可以把i绑起来算呢？[当然i可以用来判断这个位置是不是在最后一段，也可以判断这里到底能不能作为第j位]。
于是我们可以枚举长度l。
所以在可行的位置[1...n-l+1]中，最后一位是作为最后一段，其它的值是相同的，所以就是一个前缀和*这一坨+最后一个位置的特判，就可以了。
[怎么线性求组合数？] <-大家都会吧？...
不过看在我不会的份上，还是说一下吧...就是利用的是逆元的思想，C(n,r)=n!/(n-r)!/r!，那么要是预处理出所有的阶乘以及所有阶乘的逆元，每次查询就是O(1)的了...
预处理阶乘O(n)没问题，预处理出阶乘的逆元怎么办呢？...
机智的ZZD发现：1/(n-1)!=1/n!*n
%%%，先算n!的逆元，然后倒过来再乘一遍就可以了。
[上面的描述可能和代码中的含义有小小的不同，代码中l表示的是长度len-1，所以和上面有小小不同]
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; const int maxn=;
const int mod=1e9+;
typedef long long ll; int n,k;
ll s[maxn],lv[maxn],lv1[maxn];
char num[maxn];
ll ans; ll C(int n,int r){
if(r>n) return ;
if(r== || n==r) return ;
return ((lv[n]*lv1[r])%mod*lv1[n-r])%mod;
} ll power(ll a,int k){
ll ans=;
while(k){
if(k&) ans=ans*a%mod;
k>>=;a=a*a%mod;}
return ans;
} int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif scanf("%d%d",&n,&k);
scanf("%s",num+); for(int i=;i<=n;i++)
s[i]=(s[i-]+num[i]-'')%mod; lv[]=;
for(int i=;i<=n;i++)
lv[i]=lv[i-]*i%mod;
lv1[n]=power(lv[n],mod-);
for(int i=n-;i>=;i--)
lv1[i]=lv1[i+]*(i+)%mod; for(int l=;l<n;l++){
ans=(ans+(s[n-l-]*C(n-l-,k-))%mod*power(,l))%mod;
ans=(ans+((num[n-l]-'')*C(n-l-,k))%mod*power(,l))%mod;
} printf("%I64d",ans);
return ;
}