背景

2022SDwc 1day1b

题目描述

有一个长度为n的正整数序列a（下标从1开始），共有m次操作，每次操作是如下2种操作中的一个：

1 l r x：将下标区间[l,r]内的所有$a_i$都加上x。

2 l r：查询下标区间[l,r]内所有$a_i$的斐波那契数列的第$a_i$项的和，也就是f(a[l]) + f(a[l+1]) + … + f(a[r])。

其中，f(1) = f(2) = 1，f(i) = f(i-1) + f(i-2)。

格式

输入

第1行，2个正整数n,m。

第2行，n个正整数$a_i$ 。

接下来m行，每行3或4个正整数表示一个操作，格式如题面。

输出

对于每个2操作输出一行，一个整数表示答案。

由于答案可能很大，你只需要输出答案对1004535809（$=479*2 ^{21} +1$，一个质数）取模的结果。

样例

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

4
14

样例解释

对于第一个询问，f(3)+f(3)=2+2=4；

对于第二个询问，f(2)+f(7)=1+13=14。

测试限制

对于100%的数据，$n,m<=10 ^5，l<=r<=n，a_i,x<=10 ^9$。

每个测试点均为 2s, 内存限制512MB .