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

Poveste şi cerinţă...

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$

h2. Date de intrare

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

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 ($1 \le n \le 5 * 10^4$), ($1 \le q \le 2 * 10^5$), ($1 \le k \le 20$).
 
The second line of the input will contain the initial array $v$ ($1 \le v_i \le 100$).
 
The next $q$ lines of the input will contain the description of the queries. For queries of type $1$, ($1 \le a \le n$), ($1 \le b \le 100$). For queries of type $2$, ($1 \le l \le r \le n$), ($1 \le s \le 2 * 10^6$).
 
For tests worth $20$ points, ($1 \le n \le 20$).
 
For tests worth $40$ additional points, ($1 \le n \le 2000$, $1 \le q \le 5000$).
 

h2. Date de ieşire

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

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

h2. Restricţii

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

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

| 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

|
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") ==