시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.1 초 256 MB 19 11 8 53.333%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

4 4

예제 출력 1

2

예제 입력 2

6 3

예제 출력 2

0

예제 입력 3

8 8

예제 출력 3

84

출처

  • 문제를 만든 사람: 79brue