极度愤怒的小N通关了一款游戏来泄愤。

这款游戏共有 \(n\) 关，分别为第 \(0\) 关、第 \(1\) 关、第 \(2\) 关、……、第 \(n-1\) 关。这些关卡中有一些是普通关卡，另一些则是奖励关卡。

这款游戏中普通关卡与奖励关卡的分布比较特殊。如果用字符 \(\texttt{a}\) 表示普通关卡，用字符 \(\texttt{b}\) 表示奖励关卡，那么第 \(0\) 关、第 \(1\) 关、第 \(2\) 关、……、第 \(n-1\) 关依次排列形成的字符串是一个无穷字符串 \(s\) 的前缀，且 \(s\) 可以按照如下方式构造：

1. 初始时 \(s\) 为包含单个字符 \(\texttt{a}\) 的字符串。
2. 将 \(s\) 的每个字符 \(\texttt{a}\) 替换成字符 \(\texttt{b}\)，每个字符 \(\texttt{b}\) 替换成字符 \(\texttt{a}\) 得到字符串 \(t\) ，然后将 \(t\) 拼接到 \(s\) 后。
3. 不断执行 2. 得到的字符串就是最终的 \(s\) 。

可以发现 \(s=\texttt{abbabaabbaababba}\cdots\) ，所以这款游戏的第 \(0\) 关是普通关卡，第 \(1\) 关是奖励关卡，第 \(2\) 关是奖励关卡，第 \(3\) 关是普通关卡，以此类推。

通过游戏的第 \(i\) 关可以得到 \(f(i)\) 分，其中 \(f(x)=a_0 + a_1x + a_2x^2 +\cdots+ a_{k-1}x^{k-1}\) 是一个固定的 \(k-1\) 次多项式。

小N通关时一气之下通过了所有奖励关卡而忽略了所有普通关卡，然后就把游戏卸载了。现在回想起来，他想要知道他在卸载游戏前的总得分对 \(10^9 + 7\) 取模后的结果。

第一行一个正整数 \(n\)，表示游戏的关卡数目。为方便， \(n\) 以二进制表示给出。

第二行一个正整数 \(k\) ，表示多项式的次数加一。

第三行 \(k\) 个非负整数，分别为 \(a_0, a_1, a_2,\cdots, a_{k-1}\) ，表示多项式的各项系数。

一行一个非负整数，表示小N卸载游戏前的总得分对 \(10^9 + 7\) 取模后的结果。

样例1解释

这款游戏共有 \(8\) 关，通关第 \(i\) 关可以得到 \((3 + 2i + i^2)\) 分。第 \(1, 2, 4, 7\) 关为奖励关，小N 通过这几关分别得到了 \(6, 11, 27, 66\) 分，共 \(110\) 分。

数据范围

对于所有测试点： \(0\leq \log_2n\lt 5\times 10^5\) ， \(1\leq k\leq 500\) ， \(0\leq a_i\lt10^9 + 7\) ， \(a_{k-1}\neq 0\) 。