http://codeforces.com/contest/407/problem/C
You’ve got an array consisting of n integers: a[1], a[2], …, a[n]. Moreover, there are m queries, each query can be described by three integers li, ri, ki. Query li, ri, ki means that we should add to each element a[j], where li ≤ j ≤ ri.

Record means the binomial coefficient, or the number of combinations from y elements into groups of x elements.

You need to fulfil consecutively all queries and then print the final array.

Input
The first line contains integers n, m (1 ≤ n, m ≤ 105).

The second line contains n integers a[1], a[2], …, a[n] (0 ≤ ai ≤ 109) — the initial array.

Next m lines contain queries in the format li, ri, ki — to all elements of the segment li… ri add number (1 ≤ li ≤ ri ≤ n; 0 ≤ k ≤ 100).

Output
Print n integers: the i-th number is the value of element a[i] after all the queries. As the values can be rather large, print them modulo 1000000007 (109 + 7).

题意：给定一个长度为n的序列，给定m次操作，每次操作是将[l,r]范围的数依次加上C(K,K),C(K+1,K),C(K+2,K)…C(K+R-L,K)，求最后的数组。
思路：当k=0时，依次加111111；k=1时，依次加123456，k=2时，依次加1，3，6，10，15，21
；k=3时，依次加1，4，10，20，25，46。
可以发现，k=i的第j项数值等于k=i-1的前j项的前缀和，第k=i-1的数组是k=i的差分数组。
我们假定要执行一次k=2的操作，L=1，R=6
0阶差分数组：1，3，6，10，15，21
1阶差分数组：1，2，3，4 ，5 ，6，-21
2阶差分数组：1，1， 1，1，1 ，1，-6
3阶差分数组：1， 0，0，0， 0， 0，-1
开一个d[i][j]（i阶差分数组）对于每一次操作，就是d[i+1][l]++,d[j][r+1]-=C(k-i+r-l+1,k-i+1),j∈[1,k+1]
后者(抵消掉影响)的计算参考这个：

C(n-1,n-1)+C(n,n-1)+C(n+1,n-1)+…+C(n+m-1,n-1)
=C(n-1,0)+C(n,1)+C(n+1,2)+…+C(n+m-1,m)
=C(n,0)+C(n,1)+C(n+1,2)+…+C(n+m-1,m)
=C(n+m,m)

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000+100
#define mod 1000000007
#define ll long long

int n,m,a[maxn],l,r,k;
int p[200][maxn];
ll fac[maxn],inv[maxn];

ll pow_mod(int a,int n)
{
    if(n==0)return 1;
    ll x=pow_mod(a,n/2);
    x=x*x%mod;
    if(n&1)x=x*a%mod;
    return x;
}

int C(int n,int m)
{
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int main()
{
    //freopen("input.in","r",stdin);
    cin>>n>>m;
    fac[0]=1;   for(int i=1;i<maxn;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=0;i<maxn;i++)inv[i]=pow_mod(fac[i],mod-2);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&k);
        p[k+1][l]++;
        for(int i=1;i<=k+1;i++)p[i][r+1]=(p[i][r+1]+mod-C(k+1-i+r-l,k+1-i))%mod;
    }
    for(int i=100;i>=0;i--)
    {
        ll sum=0;
        for(int j=1;j<=n;j++)sum=(sum+p[i+1][j])%mod,p[i][j]=(p[i][j]+sum)%mod;
    }
    for(int i=1;i<=n;i++)printf("%d ",(a[i]+p[0][i])%mod);
    return 0;
}