有 $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$。