#45 「 宇宙矩阵 」

统计

Shanest发现宇宙的秘密与一个矩阵有关。

为了方便我们把这个矩阵表示为二维数组$G[i][j]$,其中$1 \le i < \infty, 0 \le j < 2^n$。(n为一个常数)

Shanest研究出来了这个矩阵的递推式是这样的: $$ G[i][j] = \sum_{0 \le k < 2^n}{G[i-1][k] * G[1][j \oplus k]} \ \text({\oplus为异或运算)}$$

现在给你两个数 x, y,以及G数组的第一行。

求$\sum_{0 \le i \le x}{G[2^i][y]}$的值除以$10007$的余数是多少?

输入格式

第一行三个数, $n$,$x$,$y$。

第二行$2^n$个数, 表示$G[1][i]$。

输出格式

一个整数表示答案。

样例数据

input

1 2 0
2 3

output

328

样例解释

第一组样例生成的数列为: (2,3),(13,12),(62,63),(313,312)

答案等于 2+13+313=328

数据规模与约定

$0 \le n \le 18$, $0 \le x \le 10^9$, $0 \le G[1][i] < 10007$, $0 \le y < 2^n$。

时间限制:1s

空间限制:512MB

Author: zrt