무성한 성장
시간 제한1초메모리 제한2048 MB
r행 c열 격자의 각 열에 식물을 정확히 하나씩 심고, 인접한 열의 식물이 서로 다른 행에 놓이도록 하는 방법의 수를 998244353으로 나눈 나머지로 구합니다.
문제
에디는 격자 모양의 정원을 설계하고 있다. 그는 모든 열에 식물이 정확히 하나씩 있기를 원한다. 식물끼리 자원을 두고 경쟁하지 않도록, 인접한 두 열에 있는 식물은 서로 다른 행에 있어야 한다.
이 조건을 지키면서 에디가 정원에 식물을 배치하는 방법의 수를 구하라. 어떤 칸에 식물이 있는 배치와 없는 배치가 있으면 두 배치는 다른 것으로 본다. 방법의 수가 클 수 있으므로 으로 나눈 나머지를 출력한다.
입력
첫 줄에 공백으로 구분된 두 정수 과 ()가 주어진다. 은 정원 격자의 행 수이고, 는 열 수이다.
출력
에디가 정원에 식물을 배치하는 방법의 수를 으로 나눈 나머지를 정수 하나로 출력한다.