Rampant Growth

면접 대비

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

요약
각 열에 하나씩 식물을 심되 인접한 두 열이 서로 다른 행을 쓰도록 배치하는 경우의 수를 998244353으로 나눈 나머지를 구한다.
난이도

쉬움10점 중 3점

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

문제

Eddy is planning his garden, which can be represented as a grid. He wants his garden to have exactly one plant in each column. To make sure that plants do not compete for resources, if two plants are in adjacent columns, they must be in different rows.

Compute the number of different ways he can place plants in his garden to respect the above conditions. Two ways are different if one square has a plant in one arrangement but does not have a plant in the other. Because the number of ways may be large, output the number of ways modulo 998,244,353998\\,244\\,353.

입력

The single line of input contains two space-separated integers rr and cc (1≤r,c≤50)(1 \leq r,c\leq 50), where rr is the number of rows in Eddy's garden grid, and cc is the number of columns.

출력

Output a single integer, which is the number of ways Eddy can place plants in his garden, modulo 998,244,353998\\,244\\,353.

예제3

  1. 예제 1

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

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

    입력
    42 25
    
    예상 출력
    722210361