2023 年 ? 月 ? 日。

⟦求完全图有多少个每个顶点度均为偶数的子图？⟧

“这是，不属于我的记忆？”

现在，你需要快速解决这样一道熟悉的问题..........

题目大意

一个简单图有 $n$ 个顶点，每对不同顶点之间有 $\frac{1}{2}$ 概率连边，$\frac{1}{2}$ 概率不连边（概率独立），给定数组 $c$，求使得每一个顶点 $u$，在形成的图中度数都 $\bmod 4=c_u$ 的概率。

由于点之间没有顺序区别，为了减少输入量，给出 $a_0,a_1,a_2,a_3$，$a_i:=\sum\limits_{j=1}^n[c_j=i]$。

换句话说，你可以认为 $u\in [1,a_0]$ 的 $c_u=0$，$u\in [a_0+1,a_0+a_1]$ 的 $c_u=1$，$u\in[a_0+a_1+1,a_0+a_1+a_2]$ 的 $c_u=2$，$u\in [a_0+a_1+a_2+1,n]$ 的 $c_u=3$。

本题多测。

保证模数是奇素数。

输入格式

一行两个整数 $T,p$ 分别表示数据组数和模数。

接下来 $T$ 组数据。

对于第 $i$ 组数据，先输入一行一个整数 $n_i$ 表示图的点数。接下来一行四个整数 $a_i$ 含义同题面。

输出格式

对于每组数据，输出一行一个整数，表示概率在 $\bmod p$ 意义下的值。

样例输入

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

样例输出

0
982646785
997574145
398756258
930951642

样例解释

对于第一组，有理数表示为 $0$。

对于第二组，有理数表示为 $\frac{1}{64}$。

对于第三组，有理数表示为 $\frac{11}{16384}$

数据范围

全体数据保证 $T\le 10^5,\sum n\le 10^6,p\in \mathbb{P},p\not=2,2\|\sum\limits_{i=0}^3 a_i i$。

Subtask 1 (10pts) : $T=1,n\le 7$

Subtask 2 (20pts) : $\sum n\le 40,p=998244353$

Subtask 3 (10pts) : $\sum n\le 100,p=998244353$

Subtask 4 (10pts) : $a_0=n,a_1=a_2=a_3=0$。

Subtask 5 (50pts) : $T\le 10^5,\sum n\le 10^6$