Nimber Sequence

Nimbers $a\_1, a\_2, \ldots, a\_{K-1}$, $b\_1, b\_2, \ldots, b\_5$, and $c\_1, c\_2, \ldots, c\_5$ are given.

For all $n \ge K$, the following holds.

$a\_n = \left(\bigoplus\_{i = 1}^{5} a\_{n - i} \otimes b\_i \right) \oplus \left(\bigoplus\_{i = 1}^{5} a\_{n - K + i} \otimes c\_i \right)$

Find the value of $a\_m$.

The first line contains two positive integers $K$ and $m$ ($6 \le K \le 10^5$, $1 \le m \le 10^{18}$).

The second line contains $K - 1$ non-negative integers $a\_1, a\_2, \ldots, a\_{K - 1}$ ($0 \le a\_i < 2^{32}$).

The third line contains five non-negative integers $b\_1, b\_2, \ldots, b\_5$ ($0 \le b\_i < 2^{32}$).

The fourth line contains five non-negative integers $c\_1, c\_2, \ldots, c\_5$ ($0 \le c\_i < 2^{32}$).

Output a single integer, the value of $a\_m$.

Nimbers are non-negative integers associated with Nim games. This problem needs two operations.

• $\large\oplus$ is the nim sum: $a \oplus b = \mathrm{mex}(\{a' \oplus b \mid 0 \le a' < a\} \cup \{a \oplus b' \mid 0 \le b' < b\})$.
• $\large\otimes$ is the nim product: $a \otimes b = \mathrm{mex}(\{(a' \otimes b) \oplus (a \otimes b') \oplus (a' \otimes b') \mid 0 \le a' < a, \, 0 \le b' < b\})$.

Here, $\mathrm{mex}(S)$ is the smallest non-negative integer $d$ that is not in $S$.