厭倦了計算一些稀奇古怪的問題的答案對 $998244353$ 或 $10^9+7$ 取模後的結果，小 E 設計了一道與 $2$ 相關的謎題：

給定一個 $2$ 列 $2^k$ 行的網格，你需要將 $1\sim 2^{k+1}$ 不重不漏地填入網格的 $2^{k+1}$ 個格子中，並使得相鄰格子之間的大小關係滿足下列限制。

具體地，給定三個長度分別為 $2^k-1,2^k,2^k-1$ 的 01 序列 $a,b,c$。稱一個 $2\times 2^k$ 的矩陣 $A$ 為該謎題的一組解，若且唯若其同時滿足以下四條約束：

1. $A$ 包含 $1,2,\ldots,2^{k+1}$ 中的每個整數恰好一次；
2. 對於所有 $1\le i<2^k$，均有 $a_i=[A_{1,i}<A_{1,i+1}]$；
3. 對於所有 $1\le i\le 2^k$，均有 $b_i=[A_{1,i}<A_{2,i}]$；
4. 對於所有 $1\le i<2^k$，均有 $c_i=[A_{2,i}<A_{2,i+1}]$。

其中 $[P]$ 當條件 $P$ 成立時取值為 $1$，否則為 $0$。

對你而言，僅僅找出任意一組解或判斷無解太過簡單。既然是關於 $2$ 的謎題，小 E 要求你計算謎題的解的數量對 $2$ 取模後的結果。

小 E 準備了 $t$ 道網格大小相同的謎題，並使用高效的壓縮手段將它們壓縮在一起。你需要對於其中每一道謎題，求出解的數量對 $2$ 取模後的結果。

實作細節

選手不需要，也不應該實作 main 函式。

選手需要確保提交的程式包含標頭檔 puzzle.h，即在程式開頭加入以下程式碼：

#include "puzzle.h"

選手需要在提交的程式原始碼檔案中實作以下函式：

unsigned puzzle(int t, int k, std::vector<unsigned> a,
                std::vector<unsigned> b, std::vector<unsigned> c);

• $t,k$ 分別表示謎題的個數與網格的大小。
• 對於 $0\le i<2^k-1$，$a_i$ 二進位表示中的第 $j$（$0\le j<t$）位表示第 $j+1$ 個謎題中 $A_{1,i+1}$ 與 $A_{1,i+2}$ 的大小關係的限制。
• 對於 $0\le i<2^k$，$b_i$ 二進位表示中的第 $j$（$0\le j<t$）位表示第 $j+1$ 個謎題中 $A_{1,i+1}$ 與 $A_{2,i+1}$ 的大小關係的限制。
• 對於 $0\le i<2^k-1$，$c_i$ 二進位表示中的第 $j$（$0\le j<t$）位表示第 $j+1$ 個謎題中 $A_{2,i+1}$ 與 $A_{2,i+2}$ 的大小關係的限制。
• 該函式需要回傳一個非負整數，其中二進位表示中的第 $j$（$0\le j<t$）位表示第 $j+1$ 個謎題中解的數量對 $2$ 取模後的結果。
• 對於每個測試點，該函式會被互動函式庫呼叫恰好一次。

注意：在任何情況下，互動函式庫執行所需時間均不會超過 $0.1$ 秒，所用記憶體為固定大小，且均不超過 $64$ MiB。

測試程式方式

試題目錄下的 grader.cpp 是互動函式庫參考實作，最終測試時所用的互動函式庫實作與該參考實作有所不同，因此選手的解法不應該依賴互動函式庫實作。

選手可以在本題目錄下使用如下命令編譯得到可執行程式：

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -static

對於編譯得到的可執行程式：

• 可執行檔將從標準輸入讀入以下格式的資料：
  • 輸入的第一行包含兩個正整數 $t,k$，分別表示謎題的數量與網格的大小。
  • 輸入的第 $3i-1$（$1\le i\le t$）行包含一個長度為 $2^k-1$ 的 01 字串 $a_1\ldots a_{2^k-1}$。
  • 輸入的第 $3i$（$1\le i\le t$）行包含一個長度為 $2^k$ 的 01 字串 $b_1\ldots b_{2^k}$。
  • 輸入的第 $3i+1$（$1\le i\le t$）行包含一個長度為 $2^k-1$ 的 01 字串 $c_1\ldots c_{2^k-1}$。
• 可執行檔將輸出以下格式的資料至標準輸出：
  • 輸出共 $t$ 行，其中第 $i$（$1\le i\le t$）行包含一個非負整數，表示第 $i$ 道謎題的解的數量對 $2$ 取模後的結果。

範例

輸入格式 1

2 1
1
01
1
1
00
1

輸出格式 1

1
0

輸入格式 2

4 2
100
1111
100
100
0000
110
110
1111
011
010
0000
010

輸出格式 2

1
1
0
0

附加檔案說明

在附加檔案中：

1. grader.cpp 是提供的互動函式庫參考實作。
2. puzzle.h 是標頭檔，選手不用關心具體內容。
3. template_puzzle.cpp 是提供的範例程式碼，選手可參考並實作自己的程式碼。

子任務

對於所有測試資料，均有：

• $1\le t\le 32$，$1\le k\le 18$；
• 對於所有 $1\le i<2^k$，均有 $a_i\in\{0,1\}$；
• 對於所有 $1\le i\le 2^k$，均有 $b_i\in\{0,1\}$；
• 對於所有 $1\le i<2^k$，均有 $c_i\in\{0,1\}$。

特殊性質 A：$t\le 4$。

特殊性質 B：對於所有 $1\le i<2^k$，均有 $b_i\ne b_{i+1}$。

子任務

注意：

• 選手不應當透過非法方式取得互動函式庫的內部資訊，如直接與標準輸入、輸出串流進行互動。此類行為將被視為作弊；
• 最終的評測互動函式庫與範例互動函式庫的實作不同。

本題首先會受到和傳統題相同的限制，例如編譯錯誤會導致整道題目得 $0$ 分，執行時錯誤、超過時間限制、超過空間限制等會導致相應測試點得 $0$ 分等。選手只能在程式中存取自己定義的變數以及互動函式庫給出的變數，嘗試存取其他位址空間將可能導致編譯錯誤或執行錯誤。

在上述條件基礎上：

• 對於每個測試點，程式得到滿分若且唯若呼叫 puzzle 函式時回傳的答案正確。