Star Sequence Operations

In the night sky, the stars form a sequence \(a\), where the \(i\)th element of the sequence represents the brightness of the \(i\)th star. You have two types of operations:

• Operation 1: Given in the format
  \(1\; l\; r\; x\; y\), change the brightness of every star in the segment \([l, r]\) that has brightness \(x\) to \(y\).
• Operation 2: Given in the format
  \(2\; l\; r\), compute and output the value of \[ \prod_{i=l}^{r} \binom{\sum_{j=l}^{i} a_j}{a_i} \bmod 998244353 \] where \(\binom{n}{k}\) is the binomial coefficient.

Note: All indices are 1-indexed.

inputFormat

The input begins with two integers \(n\) and \(q\) \( (1 \le n, q \le \text{small})\). The next line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the brightness of the stars. Each of the next \(q\) lines describes an operation in one of the following formats:

• 1 l r x y: For every index \(i\) with \(l \le i \le r\), if \(a_i = x\), then set \(a_i = y\).
• 2 l r: Output the value of \(\prod_{i=l}^{r} \binom{\sum_{j=l}^{i} a_j}{a_i} \bmod 998244353\).

outputFormat

For each operation of type 2, output the required value on a new line.

sample

5 3
1 2 3 2 1
2 1 5
1 2 4 2 5
2 1 5

15120
15135120