Lát Bảng Rất Dài · canuc80k4418 · Thuật toán Canuc80k

Hãy lát kín một bảng gồm $H$ hàng và $W$ cột bằng các viên không phân biệt thuộc ba loại:

ô vuông $1 \times 1$ ;
domino $1 \times 2$ ;
domino $2 \times 1$ .

Các viên phải nằm hoàn toàn trong bảng, không được chồng nhau và phải phủ mọi ô đúng một lần.

Hai cách lát được xem là khác nhau nếu có ít nhất một ô thuộc các viên khác nhau. Không đồng nhất các cách chỉ vì chúng có thể biến thành nhau bằng phép quay hoặc phản xạ.

Hãy đếm số cách lát, lấy phần dư modulo $998244353$ .

Input

Một dòng chứa hai số nguyên $H$ và $W$ .

Output

In số cách lát modulo $998244353$ .

Constraints

$1 \leq H \leq 6$ .
$1 \leq W \leq 1 0^{12}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $W \leq 8$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

2 2

Output

Giải thích: Có một cách dùng bốn ô $1 \times 1$ , bốn cách dùng đúng một domino và hai ô $1 \times 1$ , cùng hai cách dùng hai domino. Tổng cộng $1 + 4 + 2 = 7$ cách.

Ý tưởng: Với một cột, inMask cho biết các ô đã bị domino ngang từ cột trước chiếm. DFS lấp ô trống đầu tiên của cột bằng một trong ba lựa chọn: ô 1×1, domino ngang (bật bit tương ứng trong outMask), hoặc domino dọc. Số cách từ mỗi inMask sang mỗi outMask tạo thành ma trận chuyển T kích thước 2^H.
Ý tưởng: Sau mỗi cột, vector số cách được nhân với cùng ma trận T. Vì W có thể tới 10^12, tính T^W bằng bình phương nhanh. Trạng thái đầu và cuối đều là mask 0.
Đúng đắn: DFS luôn xét ô trống đầu tiên của cột. Trong mọi cách lát, ô đó thuộc đúng một trong ba loại viên nêu trên; các nhánh rời nhau và bao phủ mọi khả năng, nên T[in][out] đúng bằng số cách lấp một cột với biên tương ứng. Các cột có cùng luật, vì vậy hợp thành W cột chính là nhân T đúng W lần. Lũy thừa nhanh không thay đổi phép hợp thành, chỉ tính nó hiệu quả hơn. Phần tử từ mask 0 về mask 0 do đó là số cách lát kín toàn bảng.
Độ phức tạp: Với S=2^H≤64, nhân ma trận đặc tốn O(S^3); tổng thời gian O(S^3 log W), bộ nhớ O(S^2).