3534. 笋尖爆炸

单点时限: 3.5 sec

内存限制: 256 MB

春天到了,在春雨过后,山上长出了许多春笋,kblack 想知道山上长了多少春笋。

我们认为山上一共有 个笋窝,排成了一条直线,从 开始连续编号,第 和第 个笋窝间有山路连接 ()。

笋尖的生长速度非常惊人,我们称其为笋尖爆炸,可以用 , , , 来表示。笋尖爆炸时,从 的简单路径上,依次长出以 为前两项的斐波那契数列中对应项的春笋。例如,第 个笋窝会长出 kg 的春笋,第 个笋窝会长出 kg 的春笋,第 个笋窝会长出 kg 的春笋,而第 个笋窝会长出 kg 的春笋,以此类推。

你需要回答关于笋窝的 个询问。

输入格式

行包含 个整数,表示笋窝数 和询问数 。(

接下来 行,每行的第一个整数 表示询问的类型。

  1. ,接下来 个整数,, , , 表示发生了一次笋尖爆炸。
  2. ,接下来 个整数,, ,你需要输出从 简单路径上所有笋窝的春笋数量,结果对 取模。


输出格式

对于每个 的询问,输出一行包含询问的结果。

样例

Input
4 4
1 1 4 2 3
2 2 4
1 2 4 4 4
2 4 1
Output
16
34

提示

在春天到来前,我们认为所有笋窝都没有春笋。

13 人解决,30 人已尝试。

17 份提交通过,共有 164 份提交。

8.7 EMB 奖励。

创建: 1 年前.

修改: 1 年前.

最后提交: 2 月,1 周前.

来源: EOJ Monthly 2018.3

题目标签