== include(page="template/taskheader" task_id="arraycounting") ==

Given an array of length $n$ and a number $k$, we need to process $q$ queries of the following types:
 
$1$ $a$ $b$: Change the value of the number at position $a$ to $b$
 
$2$ $l$ $r$ $s$: Find how many arrays exist which can be formed with the numbers from positions $l$ to $r$, such that the value of each of the numbers is at least $k$ and the sum of the values is equal to $s$, if the only operation we can make is to increase values of the numbers from the array. Since the number of arrays can be really big, print the answer mod $10^9 + 7$

Poveste şi cerinţă...

h2. Date de intrare

Input file $arraycounting.in$ will contain three integers, $n$, $q$ and $k$, which represent the length of the array, the number of queries we need to process and the minimal threshold for the value of each number with respect to the second type of query.
 
The second line of the input will contain the initial array $v$.
 
The next $q$ lines of the input will contain the description of the queries.

Fişierul de intrare $arraycounting.in$ ...

h2. Date de ieşire

Output file $arraycounting.out$ will contain a line for each query of type $2$, with the answer for each query of type $2$.

În fişierul de ieşire $arraycounting.out$ ...

h2. Restricţii

* $1 ≤ n ≤ 5 * 10^4$
* $1 ≤ q ≤ 2 * 10^5$
* $1 ≤ k ≤ 20$
* $1 ≤ v[i], b ≤ 100$
* $1 ≤ a, l, r ≤ n$
* $1 ≤ s ≤ 2 * 10^6$
* For tests worth $20$ points, $1 ≤ n ≤ 20$.
* For tests worth $40$ additional points, $1 ≤ n ≤ 2000$, $1 ≤ q ≤ 5000$.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. arraycounting.in |_. arraycounting.out |

| 4 5 2
0 0 0 3
2 1 4 10
1 1 2
2 2 3 3
1 2 4
2 1 2 6
| 4
0
1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

For the first query, the arrays we can get are [$2$, $2$, $3$, $3$], [$2$, $3$, $2$, $3$], [$3$, $2$, $2$, $3$], [$2$, $2$, $2$, $4$].

...

== include(page="template/taskfooter" task_id="arraycounting") ==