题目描述

長さ $N$ の A,B,C からなる文字列 $S$ のうち、以下の条件を満たすものの個数を $2$ で割ったあまり を求めてください。

• $S$ の $1$ 文字目から $i$ 文字目までからなる文字列を $S_i$ とする。$S_i$ に含まれる A,B,C の個数をそれぞれ $A_i,B_i,C_i$ とする。このとき、$1\ \le\ i\ \le\ N$ を満たす任意の整数 $i$ に対し、以下が成り立つ。
  • $A_i-B_i\ \le\ X$
  • $B_i-C_i\ \le\ Y$
  • $C_i-A_i\ \le\ Z$

この問題は、$T$ ケース与えられます。

输入格式

入力は以下の形式で標準入力から与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

各ケースは以下の形式で与えられる。

$N$ $X$ $Y$ $Z$

输出格式

各ケースについて、答えを出力せよ。

题目大意

有 $T$ 组询问，每组询问给定 $n, X, Y, Z$。你需要计数满足如下条件的字符串 $S$：

• 长度为 $n$；
• 只包含 A、B 和 C；
• 令 $S_i$ 为 $S$ 的前 $i$ 个字符组成的串，$A_i, B_i, C_i$ 分别为 $S_i$ 中 A、B 和 C 的数量。对每个 $1\le i\le n$ 有
  • $A_i - B_i\le X$；
  • $B_i - C_i\le Y$；
  • $C_i - A_i\le Z$。

答案对 $\bm 2$ 取模。

$T\le 10,\ 1\le n\le 10^9, \ 0\le X, Y, Z\le 10^9$。

1
3 2 1 0

0

10
1 22 9 92
14 7 74 39
23 50 8 6
93 40 9 60
68 8 47 64
11 68 18 24
3 26 54 8
46 17 90 86
86 76 45 55
80 68 79 62

1
0
0
0
1
1
1
0
1
0

提示

制約

• $1\ \le\ T\ \le\ 10$
• $1\ \le\ N\ \le\ 10^9$
• $0\ \le\ X,Y,Z\ \le\ 10^9$
• 入力は全て整数である。

Sample Explanation 1

条件を満たす文字列は、AAB,AAC,ABA,ABC,ACA,ACB,BAA,BAC の $8$ 個があります。よって、解は $0$ です。