P4247 [清华集训 2012] 序列操作

**滥用评测功能将被封号。**

有一个长度为 $n$ 的序列，有三个操作： 1. `I a b c` 表示将 $[a,b]$ 这一段区间的元素集体增加 $c$； 2. `R a b`表示将 $[a,b]$ 区间内所有元素变成相反数； 3. `Q a b c` 表示询问 $[a,b]$ 这一段区间中选择 $c$ 个数相乘的所有方案的和 $\mod 19940417$ 的值。

无

无

**样例说明：** 做完第一个操作序列变为 `1 3 4 4 5`。 第一次询问结果为 $3 \times 4+3 \times 4+4 \times 4=40$。 做完 `R` 操作变成 `-1 -3 -4 -4 -5`。 做完 `I` 操作变为 `-2 -4 -5 -4 -5`。 第二次询问结果为 $-2-4-5-4-5=-20$。 **数据范围：** 对于 $100\%$ 的数据，$n \leq 50000, q \leq 50000$。初始序列的元素的绝对值 $\leq 10^9$，保证 $[a,b]$ 是一个合法区间，`I` 操作中 $|c| \leq 10^9$，`Q` 操作中 $1 \leq c \leq \min(b-a+1,20)$。