만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

이름 부르기

시간 제한5초메모리 제한1024 MB

요약
N행 M열 좌석에서 앞뒤로 붙어 앉은 두 사람의 이름이 연달아 불리지 않는 호명 순서의 수를 998244353으로 나눈 나머지로 구합니다.
난이도

보통10점 중 7점

유형
조합론, 수학, 동적 계획법
정답자
아직 제출이 없습니다

문제

스누피는 대형 강의를 들을 때면 출석을 부르는 시간이 너무 길어 따분해하곤 한다.

어느 날 심심해진 스누피는 출석을 부를 때 앞뒤로 인접한 두 사람의 이름이 연달아 불리는 경우가 생각보다 자주 있다는 것을 알아챘다. 이것이 사실인지 확인하기 위해 스누피는 직접 계산해 보기로 한다.

강의실에는 NN행 MM열의 격자 형태로 좌석이 배치되어 있고, 모든 좌석에 사람이 앉아 있다. 출석을 부를 때는 모든 사람의 이름을 정확히 한 번씩 부른다. 스누피는 출석을 부르는 모든 가능한 순서 중에서 앞뒤로 인접한 두 사람의 이름이 한 번도 연달아 불리지 않는 경우의 수를 구하려고 한다.

입력

첫째 줄에 공백을 사이에 두고 두 양의 정수 NN, MM이 주어진다. (1≤N⋅M≤500 0001 \le N \cdot M \le 500\,000)

출력

첫째 줄에 문제의 조건을 만족하는 경우의 수를 998 244 353으로 나눈 나머지를 출력한다.

예제4

  1. 예제 1

    입력
    2 1
    
    예상 출력
    0
    
  2. 예제 2

    입력
    2 2
    
    예상 출력
    8
    
  3. 예제 3

    입력
    3 2
    
    예상 출력
    152
    
  4. 예제 4

    입력
    5 3
    
    예상 출력
    278220997