만드는 중입니다

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

무성한 성장

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

요약
r행 c열 격자의 각 열에 식물을 정확히 하나씩 심고, 인접한 열의 식물이 서로 다른 행에 놓이도록 하는 방법의 수를 998244353으로 나눈 나머지로 구합니다.
난이도

쉬움10점 중 2점

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

문제

에디는 격자 모양의 정원을 설계하고 있다. 그는 모든 열에 식물이 정확히 하나씩 있기를 원한다. 식물끼리 자원을 두고 경쟁하지 않도록, 인접한 두 열에 있는 식물은 서로 다른 행에 있어야 한다.

이 조건을 지키면서 에디가 정원에 식물을 배치하는 방법의 수를 구하라. 어떤 칸에 식물이 있는 배치와 없는 배치가 있으면 두 배치는 다른 것으로 본다. 방법의 수가 클 수 있으므로 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

입력

첫 줄에 공백으로 구분된 두 정수 rr과 cc(1≤r,c≤501 \leq r,c\leq 50)가 주어진다. rr은 정원 격자의 행 수이고, cc는 열 수이다.

출력

에디가 정원에 식물을 배치하는 방법의 수를 998 244 353998\,244\,353으로 나눈 나머지를 정수 하나로 출력한다.

예제3

  1. 예제 1

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

    입력
    1 5
    
    예상 출력
    0
    
  3. 예제 3

    입력
    42 25
    
    예상 출력
    722210361