시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 256 MB0000.000%

문제

Given are Nimbers $a_1, a_2, \ldots, a_{K-1}$, $b_1, b_2, \ldots, b_5$, and $c_1, c_2, \ldots, c_5$.

Let $\displaystyle 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)$ for all $n \ge K$.

Find the value of $a_m$.

입력

The first line of input 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 line with a single integer: the value of $a_m$.

예제 입력 1

6 1000000000000000000
1 2 3 4 5
1 0 0 0 0
0 0 0 0 0

예제 출력 1

5

예제 입력 2

6 10
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

예제 출력 2

9

예제 입력 3

11 123
849 674 223 677 243 657 979 583 643 845
979 282 313 567 433
122 443 132 554 132

예제 출력 3

32098

노트

Nimbers are non-negative integers associated with Nim games. For the purposes of this problem, two operations are necessary:

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

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