T-테트로미노로 직사각형 격자판 채우기

T-테트로미노는 아래와 같은 모양이다.

$N \times M$ 크기의 직사각형 격자판이 있다. 이 격자판을 T-테트로미노로 채우는 방법은 몇 가지인가?

돌리거나 뒤집어서 같아지는 모양도 서로 다른 것으로 센다.

예를 들어 $N=4$, $M=4$일 때 방법은 아래와 같이 2가지다.

첫째 줄에 격자판의 가로 길이 $N$과 세로 길이 $M$이 주어진다. ($1 \le N \le 10^{18}$, $1 \le M \le 15$)

T-테트로미노로 격자판을 채우는 경우의 수를 998,244,353으로 나눈 나머지를 출력한다.