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

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

보드 게임

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

요약
n행 m열 격자에서 세 모서리가 검은 직사각형의 나머지 한 칸을 칠하는 규칙으로 전체를 검게 만들 수 있는, 검은 칸 수가 최소인 초기 배치의 개수를 998244353으로 나눈 나머지를 구한다.
난이도

어려움10점 중 8점

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

문제

리틀 세묜은 보드로 놀이를 한다. 처음에 세묜은 nn개의 행과 mm개의 열로 이루어진 큰 보드를 가지고 있고, 일부 칸은 검은색으로 칠해져 있다. 그리고 다음 규칙으로 다른 칸을 검은색으로 칠하기 시작한다. 어떤 직사각형의 세 꼭짓점이 이미 검은색이라면, 남은 꼭짓점도 검은색으로 칠할 수 있다. 그런데 아무 초기 보드나 세묜을 만족시키지는 않는다. 세묜은 보드 전체를 검은색으로 칠할 수 있기를 원하며, 초기 보드에 들어 있는 검은색 칸의 수는 가능한 한 적어야 한다. 여러분의 과제는 주어진 크기의 보드 중 세묜을 만족시킬 수 있는 초기 보드의 개수를 구하는 것이다.

입력

입력은 한 줄이며, 두 정수 nn과 mm (1≤n,m≤1091 \le n, m \le 10^9)이 주어진다. 각각 행과 열의 개수이다.

출력

세묜을 만족시키는 보드의 개수를 출력한다. 이 수는 매우 클 수 있으므로 소수 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

힌트

두 번째 예제에서 세묜을 만족시키는 보드는 정확히 검은색 칸이 33개인 보드이다.

예제2

  1. 예제 1

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

    입력
    2 2
    
    예상 출력
    4