十六夜咲夜在幻想乡论坛看到了这样一个帖子：帖子中有一只兔子和一些妖精的回复，帖子回复共有 条，从上往下排成一列，其中第 条回复的类型为 ，兔子和妖精总共会进行三种类型的回复（冒号前面表示发送者，冒号后表示内容）：
类型一：「兔子：兔子楼上」；
类型二：「兔子：兔子楼下」；
类型三：「妖精：缓缓打出？？」。
显然，回复类型一要求这条回复存在下一条回复、且发送者是兔子；回复类型二要求这条回复存在上一条回复、且发送者是兔子；回复类型三没有额外要求，此时认为这些回复是合法的。

现在这个帖子缺失了一些回复，这些缺失的回复用 表示，现在你需要处理 次操作或询问：
对于操作，给定 ，将第 条回复的类型改为 ；
对于询问，给定 ，询问如果我们将子序列 视为一个全新且独立的帖（即 是第一条回复， 是最后一条回复），有多少种方法可以补全其中的缺失回复（ 的那些），使得这个新序列是合法的。由于答案可能很大，请将答案对 取模后输出。若不存在合法方案则输出 。

第一行输入两个整数 ，表示帖子长度和询问次数。
第二行输入  个整数 ，表示帖子第  条回复的类型。
此后  行，每行输入先输入一个整数 ，表示操作类型，随后在同一行：
若 ，输入两个整数 ，表示将第  条回复的类型改为 ；
若 ，输入两个整数 ，表示询问的区间。数据保证至少存在一次询问。

对于每次询问，新起一行输出一个整数，表示对应询问的答案，对  取模。若不存在合法方案则输出 。

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

1
2
2
5

8 6
0 1 0 2 3 0 2 0
1 1 0
2 2 5
1 3 0
2 4 7
1 5 0
2 2 7

2
0
10