题目背景

QAQ

题目描述

给定数列$a_1...a_n$及$x_0$。

满足

$$f[i][j]=\begin{cases} a_i & j=0,i<=n \\ x_0 & j=0,i=n+1 \\ f[i][j-1]+f[i-1][j-1] & 0<i,j<=n+1,j<i \\ 0 & i<=j \\ \end{cases} $$

求

$$\sum_{i=0}^{n+1}\sum_{j=0}^{n+1}f[i][j]$$

但这样太水了

于是给出$m$个操作，每次将$a[l]...a[r] \ (0\le l,r \le n)$加$p$，对于每个操作，输出答案。

特别地，若$0$在$l...r$范围内，我们认为$x_0$也加$p$。

另外，在读入$m$个操作前，你也应该输出答案。

由于答案可能过大，输出答案对$1234567891$取模的结果。

输入格式

第一行，两个整数$n,m$。

下面一行$n+1$个整数，为$a_1...a_n$及$x_0$，且最后一个是$x_0$。

下面$m$行，每行$3$个整数$l,r,p$。

输出格式

共$m+1$行，每行一个整数，为答案。

2 2
1 2 3
1 2 3
0 1 3

22
46
64

提示

共20个数据点。

对于第$i$个数据点

$$n,m=\lfloor ln^{12}i+\pi^5\rfloor,|a,x,p|\le \lfloor ln^{19}i+i^{\pi}\rfloor $$

保证$0 \le l\le r \le n$

想不到吧！