There are $2n$ bots, numbered $1$ to $2n$. You want to divide them into two groups, each containing $n$ bots, using the following process:

• All bots, in increasing order of their numbers, flip a fair coin (the probability of heads or tails is $0.5$).
• If the coin lands heads, the bot is assigned to group A, unless group A already has $n$ bots (in which case it is assigned to group B).
• If the coin lands tails, the bot is assigned to group B, unless group B already has $n$ bots (in which case it is assigned to group A).

There are $q$ independent queries. Each query provides $k$ bot numbers $b_1, \dots, b_k$. Calculate the probability that these $k$ bots are assigned to the same group. The answer should be modulo $998244353$.

Input

The first line contains two positive integers $n$ and $q$.

The next $q$ lines each start with a positive integer $k$, followed by $k$ positive integers $b_1, \dots, b_k$. It is guaranteed that $b_i > b_{i-1}$.

Output

For each query, output a single non-negative integer on a new line, representing the answer modulo $998244353$.

Examples

Input 1

2 6
2 1 2
2 1 3
2 1 4
2 2 3
2 2 4
2 3 4

Output 1

499122177
748683265
748683265
748683265
748683265
499122177

Note 1

Taking the second query as an example, we need to find the probability that the first and third bots are in the same group.

There are 16 equally likely outcomes for the four bots flipping coins:

1. HHHH
2. HHHT
3. HHTH
4. HHTT
5. HTHH
6. HTHT
7. HTTH
8. HTTT
9. THHH
10. THHT
11. THTH
12. THTT
13. TTHH
14. TTHT
15. TTTH
16. TTTT

Among these, cases 5, 6, 11, and 12 satisfy the condition that the first and third bots are in the same group. The probability is $4/16 = 0.25$, which is $748683265 \pmod{998244353}$.

Input 2

3 5
3 2 3 5
2 2 4
2 5 6
3 1 4 6
2 2 5

Output 2

935854081
623902721
374341633
935854081
686292993

Input 3

See the provided files ex_flip3.in and ex_flip3.ans. This sample satisfies the special properties of Subtask 2.

Input 4

See the provided files ex_flip4.in and ex_flip4.ans. This sample satisfies the special properties of Subtask 7.

Constraints

This problem uses bundled testing.

For all data, $2 \le n \le 10^5$, $1 \le q \le 10^5$, $1 \le b_i \le 2n$, $b_i > b_{i-1}$, $2 \le k \le n$, and $\sum k \le 2 \times 10^5$.

• Subtask 1 (9 points): $n \le 8, q \le 5$.
• Subtask 2 (14 points): $n \le 10$.
• Subtask 3 (7 points): $n \le 100, q = 1$.
• Subtask 4 (15 points): $q = 1$.
• Subtask 5 (6 points): $k = 2$.
• Subtask 6 (8 points): $b_k = 2n$.
• Subtask 7 (8 points): $\sum (b_k - b_1) \le 5 \times 10^5$.
• Subtask 8 (33 points): No special restrictions.