[Date: ? ?, 2023.]

[Question: How many subgraphs of a complete graph have all vertices with even degrees?]

"Is this... a memory that does not belong to me?"

Now, you need to quickly solve such a familiar problem..........

Problem Statement

A simple graph has $n$ vertices. Each pair of distinct vertices is connected by an edge with probability $\frac{1}{2}$ and not connected with probability $\frac{1}{2}$ (independently). Given an array $c$, find the probability that for every vertex $u$, the degree of $u$ in the resulting graph satisfies $\text{deg}(u) \equiv c_u \pmod 4$.

Since the vertices are indistinguishable, to reduce the input size, we are given $a_0, a_1, a_2, a_3$, where $a_i := \sum_{j=1}^n [c_j = i]$.

In other words, you can assume $c_u = 0$ for $u \in [1, a_0]$, $c_u = 1$ for $u \in [a_0+1, a_0+a_1]$, $c_u = 2$ for $u \in [a_0+a_1+1, a_0+a_1+a_2]$, and $c_u = 3$ for $u \in [a_0+a_1+a_2+1, n]$.

This problem involves multiple test cases.

It is guaranteed that the modulus is an odd prime.

Input

The first line contains two integers $T$ and $p$, representing the number of test cases and the modulus, respectively.

Then $T$ test cases follow.

For each test case, the first line contains an integer $n_i$, representing the number of vertices in the graph. The next line contains four integers $a_0, a_1, a_2, a_3$ as defined in the problem statement.

Output

For each test case, output a single integer representing the probability modulo $p$.

Examples

Input 1

5 998244353
4
2 0 2 0
4
0 3 0 1
6
6 0 0 0
40
10 5 18 7
100
30 11 30 29

Output 1

0
982646785
997574145
398756258
930951642

Note

For the first case, the rational value is $0$.

For the second case, the rational value is $\frac{1}{64}$.

For the third case, the rational value is $\frac{11}{16384}$.

Constraints

It is guaranteed that $T \le 10^5$, $\sum n \le 10^6$, $p \in \mathbb{P}$, $p \neq 2$, and $2 \mid \sum_{i=0}^3 a_i i$.

• Subtask 1 (10 pts): $T = 1, n \le 7$
• Subtask 2 (20 pts): $\sum n \le 40, p = 998244353$
• Subtask 3 (10 pts): $\sum n \le 100, p = 998244353$
• Subtask 4 (10 pts): $a_0 = n, a_1 = a_2 = a_3 = 0$
• Subtask 5 (50 pts): $T \le 10^5, \sum n \le 10^6$