Niuniu has learned prefix sum and he found an interesting about prefix sum.
Let's consider (k+1) arrays a[i] (0 <= i <= k)
The index of a[i] starts from 1.
a[i] is always the prefix sum of a[i-1].
"always" means a[i] will change when a[i-1] changes.
"prefix sum" means a[i][1] = a[i-1][1] and a[i][j] = a[i][j-1] + a[i-1][j] (j >= 2)
Initially, all elements in a[0] are 0.
There are two kinds of operations, which are modify and query.
For a modify operation, two integers x, y are given, and it means a[0][x] += y.
For a query operation, one integer x is given, and it means querying a[k][x].
As the result might be very large, you should output the result mod 1000000007.
