Two players play following game. Initially they have number $$$ n $$$. Players make alternating turns. If the current number written on the board is more than $$$ 0 $$$ during his move the player can divide the current number by $$$2$$$ with rounding down or substract $$$ 1$$$ from the current number, but such a move can be made only when the current number is odd. (that is, $$$ 4 $$$ per move can be turned into $$$ 2 $$$, and $$$ 7 $$$ into $$$ 3 $$$ or $$$ 6 $$$). The game continues until number $$$ 0 $$$ appears on the board. The player who cannot make a move loses (that is, the player who is forced to move when the number $$$ 0 $$$ is written on the board). Determine who wins if both players play optimally – the one who moved first or the one who moved second. You need to answer $$$ t $$$ independent queries. For each of them print $$$ 1 $$$ if for the given $$$ n $$$ the first player wins, and $$$ 0 $$$ otherwise. Print the answers to the queries in the order in which they appear in the input data.

Let's define function $$$f$$$ from array of non-negative numbers $$$A$$$ of $$$n$$$ elements in the following way: $$$f(A, 0) = $$$ $$$\sum\limits_{i=1}^n a_i$$$;

$$$f(A, i) = $$$$$$\sum\limits_{l=1}^n \sum\limits_{r=l}^n$$$ $$$f(A[l, r], i - 1)$$$, $$$i \gt 0$$$, where $$$A[l, r]$$$ - subarray of array $$$A$$$ with indexes from $$$l$$$ to $$$r$$$. You are given $$$n$$$, $$$k$$$ and array $$$A$$$ of $$$n$$$ elements. Compute $$$f(A, k)$$$ modulo $$$10^9+7$$$.

Krosh has a graph of $$$n$$$ vertexes. For any vertex $$$1 \le i \le n - 2$$$ there are oriented edges $$$(i, i + 1)$$$ and $$$(i, i + 2)$$$, for vertex $$$n - 1$$$ there is oriented edge $$$(n - 1, n)$$$. Every vertex has it's value - $$$a_i$$$. Krosh considers paths from vertex $$$1$$$ to vertex $$$n$$$. Cost of the path is the maximum among all the values of the vertexes Krosh has visited. Help Krosh to calculate sum of costs over all the paths from $$$1$$$ to $$$n$$$. Output answer modulo $$$m$$$ where $$$m$$$ is given(can be non-prime).

Krosh calls positive integer interesting if it can be represented as a sum of two powers of number two, in other words $$$x$$$ is interesting if there exists two non-negative numbers $$$i \ge 0$$$, $$$j \ge 0$$$, $$$i \neq j$$$ such that $$$x = 2^i + 2^j$$$. Krosh has big number $$$m$$$ in binary number system. Length of this number does not exceed $$$2*10^5$$$. Help Krosh to calculate how many interesting numbers there are from $$$1$$$ to $$$m$$$.

You are given number $$$n$$$. Find number of ways to decompose number $$$n$$$ on summands where each next summand is at least twice more than the previous. So for each $$$1 \le i \lt k$$$ where $$$k$$$ is number of summands $$$a_{i + 1} \ge 2 * a_i$$$.

Krosh has given a new math homework: find the sum of the following series: $$$\sum\limits_{n = 1}^{\infty} \frac{(C_n^k) ^ 2}{2^n}$$$, where $$$k$$$ is given. Help him to find it for given $$$k$$$. It's guaranteed that answer is integer. Print it modulo prime number $$$10^9+7$$$.

You are given number $$$n$$$. Consider permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$. Define $$$f(l, r) = (((p(l)$$$ $$$mod$$$ $$$p(l + 1))$$$ $$$mod$$$ $$$p(l + 2))$$$ $$$mod$$$ ... $$$mod$$$ $$$p(r)$$$. Let's beauty of permutation $$$B(p)$$$be the sum $$$f(l, r)$$$ over all the subsegments of permutation $$$B(p) = \sum_{l = 1}^n \sum_{r = l}^n f(l, r)$$$. Find expectation of the beauty of randomly chosen permutation of $$$n$$$ integers over given prime modulo $$$m$$$. It can be shown that answer can be represented as fraction $$$\frac{P}{Q}$$$, where $$$P$$$, $$$Q$$$ are integers and $$$Q \neq 0$$$ $$$(mod$$$ $$$m)$$$.

Krosh is going to celebrate his birthday soon. He thinks that friends will present him some permutation $$$p$$$ of $$$n$$$ numbers from $$$1$$$ to $$$n$$$. Krosh may dislike permutation because he likes fixed points. These are such positions $$$i$$$ where $$$p_i = i$$$. He wants permutation to contatin at least one fixed point. So he can do following moves with the presented permutation: swap any two adjacent elements in it. Krosh knows how to make minimum number of moves to obtain his goal but there is a new question for him: what is the maximum number of such moves he can do in worst scenario?

Krosh has three numbers $$$ a $$$, $$$ b $$$, $$$ c $$$. Help him count the number of arrays of length $$$ n $$$, whose $$$ AND $$$ of elements is equal to $$$ a $$$, $$$ OR $$$ of elements is equal to $$$ b $$$, and $$$ XOR $$$ of elements is equal to $$$ c $$$. Two arrays are considered different if there is a position such that different arrays have different numbers at this position. Since the answer can get big, print its remainder after division by $$$ 10 ^ 9 + 7 $$$.

Consider some number without leading zeroes(but 0 is allowed). We neee to obtain new number which is divisible by three. In one move we can take any digit of this number and decrease it(if it is not 0) or increase it by 1(if it is not 9). Resulting number should not contain leading zeroes(but 0 is allowed). What is the minimum number of such moves to get a number which is divisible by three?