아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

유리크와 목공 수업

시간 제한1초메모리 제한512 MB

요약
N×M 보드에서 왼쪽 위와 오른쪽 아래 칸을 남기고, 남은 칸이 서로 연결되며 모든 행과 열에서 연속되도록 칸을 잘라내는 경우의 수를 998244353으로 나눈 나머지로 구합니다.
난이도

어려움10점 중 8점

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

문제

오늘 유리크는 기분이 아주 좋아서 아침 일찍 일어났다. 시간표에 따르면 첫 수업이 목공 수업이기 때문이다. 이 수업은 유리크가 제일 좋아하는 수업이다. 보통은 선생님 말씀을 듣지 않고 교실 뒤에서 친구들과 보드게임을 하기 때문이다. 그런데 오늘 시험을 본다는 것을 알고 실망했다.

수업을 시작할 때 선생님이 학생마다 N×MN \times M 크기의 나무판을 하나씩 나누어 주었다. 연필로 그은 선이 나무판을 NN개의 행과 MM개의 열로 나누고, 나무판은 크기가 1×11 \times 1인 정사각형 칸 N⋅MN \cdot M개로 이루어져 있다.

시험은 톱으로 나무판의 일부 칸을 잘라 내어 남은 부분을 아름다운 판으로 만드는 것이다. 판이 다음 다섯 조건을 모두 만족하면 아름다운 판이다.

  1. 판의 왼쪽 위 칸은 잘리지 않았다.
  2. 판의 오른쪽 아래 칸은 잘리지 않았다.
  3. 남은 칸들이 하나로 연결되어 있다. 어떤 칸에서든 왼쪽, 오른쪽, 위, 아래로 인접한 칸을 거쳐 다른 모든 칸에 갈 수 있다.
  4. 각 행에서 남은 칸들이 하나의 연속된 가로 구간을 이룬다.
  5. 각 열에서 남은 칸들이 하나의 연속된 세로 구간을 이룬다.

이 조건 중 하나라도 만족하지 않는 판은 추한 판이다. 아래 그림은 3×43 \times 4 크기의 아름다운 판과 추한 판의 예시이다. 왼쪽 위 칸과 오른쪽 아래 칸은 회색으로 칠해져 있다.

유리크는 선생님 말씀을 듣지 않고 수학을 좋아해서, 시험 대신 다른 질문을 떠올렸다. 원래 나무판에서 일부 칸을 잘라 내어 만들 수 있는 서로 다른 아름다운 판은 몇 개인가? 잘라 낸 칸의 집합이 다르면 서로 다른 판으로 센다. 칸을 하나도 자르지 않는 경우도 포함한다.

유리크가 이 질문에 답하도록 도와라.

입력

입력은 한 줄이며, 원래 나무판의 크기를 나타내는 두 정수 NN과 MM이 주어진다 (1≤N,M≤1051 \le N, M \le 10^5).

출력

원래 나무판에서 일부 칸을 잘라 내어 만들 수 있는 서로 다른 아름다운 판의 개수를 한 줄에 출력하라. 답이 매우 클 수 있으므로 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

힌트

아래 그림은 2×22 \times 2 나무판에서 잘라 낼 수 있는 아름다운 판 전부와, 2×42 \times 4 나무판에서 잘라 낼 수 있는 아름다운 판 전부를 보여 준다.

예제3

  1. 예제 1

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

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

    입력
    100 100
    
    예상 출력
    818380736