Đếm số cách đặt các quân domino \(1\times 2\) hoặc \(2\times 1\) lên bảng hình chữ nhật \(m \times n\). Lưu ý, các quân domino không cần phải lấp đầy bảng và không đặt quân domino nào cũng được tính là một cách.

Một ví dụ cho trường hợp \(m = 2, n = 2\):

Input

• Gồm dòng duy nhất chứa 2 số nguyên dương \(m, n\) (\(1 \leq m \leq 2\), \(1 \leq n \leq 10^{12}\)).

Output

• Gồm một số nguyên dương là số cách đặt các quân domino sau khi chia lấy dư cho \(998244353\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m = 1\), \(n \leq 20\).
• Subtask \(2\) (\(25\%\) số điểm): \(m = 1\), \(n \leq 10^5\).
• Subtask \(3\) (\(25\%\) số điểm): \(m = 2\), \(n \leq 10\).
• Subtask \(4\) (\(20\%\) số điểm): \(m = 2\), \(n \leq 10^5\).
• Subtask \(5\) (\(10\%\) số điểm): \(m = 2\), \(n \leq 10^{12}\).

Example

1 3

3

2 2

7