输入描述:

第一行输入两个正整数表示高塔的层数，以及询问的次数。
第二行输出一个长度大小为的字符串，字符串仅包括。
接下来行，每行首先输入一个非负整数表示操作的类型。

当时，表示这是一个修改操作。
接下来还会继续输入一个正整数和一个字符，表示第层的塔结构变为。

当时，表示这是一个查询操作。
接下来还会继续输入四个整数，分别表示智乃酱一开始的层数，她想去的层数。
当为0时，表示一开始在左边的塔，否则表示一开始在右边的塔。
当为0时，表示她的终点为左边的塔，否则表示终点为右边的塔。

输出描述:

对于每一个输出一行，每行一个正整数表示方案数对取余数后的结果。