3534. 笋尖爆炸

单测试点时限: 3.5 秒

内存限制: 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

提示

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

12 人解决,29 已尝试。

16 份提交通过,共有 157 份提交。

8.8 EMB 奖励。

创建: 8 月,2 周前.

修改: 8 月,2 周前.

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

来源: EOJ Monthly 2018.3

标签