小蓝考上了世界上最好的魔法师学校，然而入学第一件事就是智力测试，老师给出了一个 大小的棋盘，同时对每行每列设置了权重 和 ，因此，对于第 行第 列的格子 ，其权重为一个二元组 。
小蓝可以在格子之间进行移动，若某时刻小蓝在格子 ，那么他可以一步走到任意的格子 或 ，其中 满足：
（1），
（2）。
之后，老师提出了 个问题，第 个问题为：假设小蓝从格子 出发，移动到格子 有多少种不同的走法，答案对 取模。
输入的第一行包含三个正整数 ，相邻整数之间使用一个空格分隔。
第二行包含 个正整数 ，相邻整数之间使用一个空格分隔。
第三行包含 个正整数 ，相邻整数之间使用一个空格分隔。
接下来 行，第 行包含四个正整数 ，相邻整数之间使用一个空格分隔。
输出 行，每行包含一个整数，依次表示每个问题的答案。
4 4 2 4 2 3 1 2 1 2 1 4 4 1 1 2 2 2 4
4 0
【样例说明】
询问 1：
询问 2：
【评测用例规模与约定】
对于 的评测用例，；
对于所有评测用例，，，，。
