Tiling with T-tetrominoes

시간 제한0.1초메모리 제한256 MB

요약

N 곱하기 M 격자를 T-테트로미노로 채우는 경우의 수를 998244353으로 나눈 나머지를 구한다. 회전과 뒤집기는 서로 다른 배치로 센다. N은 10^18까지, M은 15까지 주어진다.

문제

T-tetromino는 아래와 같은 모양을 말한다.

N×M 크기의 직사각형 격자판이 있다. 이 격자판을 T-tetromino로 채우는 경우의 수는 몇 가지일까?

돌리거나 뒤집어서 같은 모양도 따로 센다.

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

첫째 줄에 직사각형 격자판의 가로 길이 N과 세로 길이 M이 주어진다. (1 ≤ N ≤ 1018, 1 ≤ M ≤ 15)

T-tetromino로 직사각형 격자판을 채우는 경우의 수를 998,244,353으로 나눈 나머지를 출력한다.