Description

Uncle Fang has some blank playing cards. He wants to use them to play a math game.

He first decides to form $m$ piles from these blank cards, with the size of each pile being an integer power of $2$. Specifically, the $i$-th pile (note: indexed from $0$) will have $2^{n_i}$ cards. He first decides that pile $0$ has $2^{n_0}$ cards, and then labels the cards in this pile from top to bottom with the decimal numbers $1 \sim 2^{n_0}$ in order.

Before starting the game, Uncle Fang decides to shuffle, and he decides to shuffle $x_0$ times. He has a fixed shuffling pattern: each shuffle is equivalent to the following two steps:

1. Take out all cards in odd positions (counted from the top) in order to form a new pile.
2. Place this new pile on top of the remaining old pile.

For example, when $n_0 = 3$, pile $0$ starts from top to bottom as 12345678'', after one shuffle it becomes 13572468'', and after two shuffles it becomes ``15263748''.

After shuffling, Uncle Fang decides to add a number $t_0$ to the labels of the cards from the $l_0$-th to the $r_0$-th from top to bottom. He then converts these labels to binary and XORs them in order to obtain a value; he records the value modulo $2^{n_0-1}$ as $\mathrm{ans}_0$.

Similarly, Uncle Fang will play with the remaining $m-1$ piles in the same way. Specifically, he decides to operate on each pile according to the following formulas:

1. For the $i$-th pile, the pile will have $2^{n_i}$ cards, labeled from top to bottom with the decimal integers $1 \sim 2^{n_i}$. Here, $n_i = (\mathrm{ans}_{i-1} + i - 1) \bmod 5 \mathrel{+} \mathrm{Base}$, where $\mathrm{Base}$ is a positive integer decided in advance.
2. He first decides the position of the first card he will look at, denoted by $l_i$, where $l_i = (2\mathrm{ans}_{i-1} + l_{i-1} + i - 1) \bmod 2^{n_i} \mathrel{+} 1$.
3. He then decides the position of the last card he will look at, denoted by $r_i$, where $r_i = \bigl(\mathrm{ans}_{i-1} + 1 + 2^{\lfloor n_i/2 \rfloor}(l_i \bmod 2^{\lfloor n_i/2 \rfloor})\bigr) \bmod 2^{n_i} \mathrel{+} 1$.
4. Since the above two formulas are not simple, it is possible that $l_i > r_i$. In that case, swap their values.
5. After deciding which cards to look at, he decides to shuffle $x_i$ times, where $x_i = (r_i - l_i + t_{i-1} + i - 1) \bmod 2^{n_i}$.
6. He also decides the number $t_i$ to add to each selected card, where $t_i = (l_i + r_i) \bmod 2^{n_i}$.
7. After shuffling, he adds $t_i$ to each card from the $l_i$-th to the $r_i$-th from top to bottom, converts them to binary and XORs them in order to obtain a value; he records the value modulo $2^{n_i-1}$ as $\mathrm{ans}_i$, and then returns to Step 1 to play with the next pile.

Uncle Fang has heard about your outstanding informatics skills. He wants to know whether you can compute in advance the game result $\mathrm{ans}_{m-1}$ for the last pile, i.e., pile $m-1$. Can you do it?

Input Format

The first line contains an integer $m$, the number of piles.

The next line contains six integers: $n_0, x_0, l_0, r_0, t_0, \mathrm{Base}$.

Output Format

Output a single integer, the final answer.

2
5 1 4 27 3 15

2700

Hint

Constraints

• For $10\%$ of the testdata, $m \le 100$.
• For $20\%$ of the testdata, $m \le 5\times 10^5$, $n_i \le 20$, $\mathrm{Base} \le 16$.
• For $60\%$ of the testdata, $m \le 5\times 10^5$, $n_i \le 60$, $\mathrm{Base} \le 55$.
• For all testdata, $m \le 5\times 10^6,\ n_i \le 60,\ 0 < l_i \le r_i \le 2^{n_i},\ 0 < x_i, t_i < 10^9,\ \mathrm{Base} \le 55$.

Sample Explanation $\mathrm{ans}_0 = 1$, $n_1 = 16$, $l_1 = 7$, $r_1 = 1795$, $x_1 = 1791$, $t_1 = 1802$.

Translated by ChatGPT 5