智乃酱的双塔问题
题号：NC223137
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

如图所示，在某个地方有两座层数为的高塔，两座高塔的内部各自都有连接到上一层的楼梯，即每座塔的第层可以直接上楼梯到第层。
同时，在两座高塔之间还会存在一些连接两座高塔的楼梯，具体来说，除了顶层以外，每一层都是以下这两种情况之一。
  1. 左侧高塔的第层有楼梯连接右侧高塔的第层。
  2. 右侧高塔的第层有楼梯连接左侧高塔的第层。
我们用字符'/'表示第1种情况，用字符'\'表示第二种情况。现在智乃想知道，她从某座高塔的第层移动到层（），在只能走楼梯上楼的情况下，有多少种不同的移动方案？
为了避免这个数字太大，你只用输出方案数对取余数后的结果即可。

输入描述:

第一行输入两个正整数表示高塔的层数，以及询问的次数。
第二行输出一个长度大小为的字符串，字符串仅包括。
接下来行，每行四个整数，分别表示智乃酱一开始的层数，她想去的层数。
当为0时，表示一开始在左边的塔，否则表示一开始在右边的塔。
当为0时，表示她的终点为左边的塔，否则表示终点为右边的塔。

输出描述:

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

输入

复制 
4 5
//\
1 4 0 0
2 4 0 0
2 4 0 1
3 4 0 1
3 4 1 0

输出

复制 
3
2
1
0
1

说明

样例如题目描述中的图所示。
对于第一组查询：
从左边的塔第1层爬到左边的塔第4层共有3种方案：
1.直接在左侧塔内移动到第4层。
2.从左侧塔1层移动到右侧的塔2层，然后从右侧塔上楼移动到3层，最后从右侧塔3层移动到左侧塔4层。
3.先上楼，然后从左侧塔2层移动到右侧的塔3层，最后从右侧塔3层移动到左侧塔4层。