Niuniu has learned prefix sum and he found an interesting about prefix sum. Let's consider (k+1) arrays a[i] (0
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.
（图片来源网络，侵删）
