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.
输入描述:
The first line contains three integers, n, m, k.
n is the length of each array.
m is the number of operations.
k is the number of prefix sum.
In the following m lines, each line contains an operation.
If the first number is 0, then this is a change operation.
There will be two integers x, y after 0, which means a[0][x] += y;
If the first number is 1, then this is a query operation.
There will be one integer x after 1, which means querying a[k][x].
1 <= n <= 100000
1 <= m <= 100000
1 <= k <= 40
1 <= x <= n
0 <= y < 1000000007
输出描述:
For each query, you should output an integer, which is the result.
示例1
输入
复制
4 11 3
0 1 1
0 3 1
1 1
1 2
1 3
1 4
0 3 1
1 1
1 2
1 3
1 4
说明
For the first 4 queries, the (k+1) arrays are
1 0 1 0
1 1 2 2
1 2 4 6
1 3 7 13
For the last 4 queries, the (k+1) arrays are
1 0 2 0
1 1 3 3
1 2 5 8
1 3 8 16