Description
极度愤怒的小 N 通关了一款游戏来泄愤。
这款游戏共有 n 关，分别为第 0 关、第 1 关、第 2 关、 · · ·、第 n − 1 关。这些关
卡中有一些是普通关卡，另一些则是奖励关卡。
这款游戏中普通关卡与奖励关卡的分布比较特殊。如果用字符 a 表示普通关卡，用
字符 b 表示奖励关卡，那么第 0 关、第 1 关、第 2 关、 · · ·、第 n − 1 关依次排列形成
的字符串是一个无穷字符串 s 的前缀，且 s 可以按照如下方式构造：
1. 初始时 s 为包含单个字符 a 的字符串。
2. 将 s 的每个字符 a 替换成字符 b，每个字符 b 替换成字符 a 得到字符串 t，然后
将 t 拼接到 s 后。
3. 不断执行 2. 得到的字符串就是最终的 s。
可以发现 s = abbabaabbaababba · · ·，所以这款游戏的第 0 关是普通关卡，第 1 关
是奖励关卡，第 2 关是奖励关卡，第 3 关是普通关卡，以此类推。
通过游戏的第 i 关可以得到 f(i) 分，其中 f(x) = a0 + a1x + a2x2 + · · · + ak−1xk−1
是一个固定的 k − 1 次多项式。
小 N 通关时一气之下通过了所有奖励关卡而忽略了所有普通关卡，然后就把游戏
卸载了。现在回想起来，他想要知道他在卸载游戏前的总得分对 10^9 + 7 取模后的结果。
这款游戏共有 n 关，分别为第 0 关、第 1 关、第 2 关、 · · ·、第 n − 1 关。这些关
卡中有一些是普通关卡，另一些则是奖励关卡。
这款游戏中普通关卡与奖励关卡的分布比较特殊。如果用字符 a 表示普通关卡，用
字符 b 表示奖励关卡，那么第 0 关、第 1 关、第 2 关、 · · ·、第 n − 1 关依次排列形成
的字符串是一个无穷字符串 s 的前缀，且 s 可以按照如下方式构造：
1. 初始时 s 为包含单个字符 a 的字符串。
2. 将 s 的每个字符 a 替换成字符 b，每个字符 b 替换成字符 a 得到字符串 t，然后
将 t 拼接到 s 后。
3. 不断执行 2. 得到的字符串就是最终的 s。
可以发现 s = abbabaabbaababba · · ·，所以这款游戏的第 0 关是普通关卡，第 1 关
是奖励关卡，第 2 关是奖励关卡，第 3 关是普通关卡，以此类推。
通过游戏的第 i 关可以得到 f(i) 分，其中 f(x) = a0 + a1x + a2x2 + · · · + ak−1xk−1
是一个固定的 k − 1 次多项式。
小 N 通关时一气之下通过了所有奖励关卡而忽略了所有普通关卡，然后就把游戏
卸载了。现在回想起来，他想要知道他在卸载游戏前的总得分对 10^9 + 7 取模后的结果。
Input
第一行一个正整数 n，表示游戏的关卡数目。为方便， n 以二进制表示给出。
第二行一个正整数 k，表示多项式的次数加一。
第三行 k 个非负整数，分别为 a0, a1, a2, ... ,ak-1，表示多项式的各项系数。
第二行一个正整数 k，表示多项式的次数加一。
第三行 k 个非负整数，分别为 a0, a1, a2, ... ,ak-1，表示多项式的各项系数。
Output
一行一个非负整数，表示小 N 卸载游戏前的总得分对 10^9 + 7 取模后的结果。
Sample Input Copy
样例1：
1000
3
3 2 1
110
样例2：
11111100101
4
2 0 2 1
样例3：
1001011001101001
16
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1Sample Output Copy
样例1
110
样例2
143901603
样例3
184740992HINT
样例1：
这款游戏共有 8 关，通关第 i 关可以得到 (3 + 2i + i2) 分。第 1, 2, 4, 7 关为奖励关，
小 N 通过这几关分别得到了 6, 11, 27, 66 分，共 110 分。
对于所有测试点： 0 ≤ log2 n < 5 × 10^5， 1 ≤ k ≤ 500， 0 ≤ ai < 10^9 + 7， ak-1 != 0。
这款游戏共有 8 关，通关第 i 关可以得到 (3 + 2i + i2) 分。第 1, 2, 4, 7 关为奖励关，
小 N 通过这几关分别得到了 6, 11, 27, 66 分，共 110 分。
对于所有测试点： 0 ≤ log2 n < 5 × 10^5， 1 ≤ k ≤ 500， 0 ≤ ai < 10^9 + 7， ak-1 != 0。