시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB75312640.000%

문제

승원이는 수열과 쿼리 998244353을 풀던 도중 도저히 풀이가 떠오르지 않아 옆자리에 있던 민재와 게임을 하려고 한다. 게임의 규칙은 아래와 같다.

  • 게임은 높이가 $K$인 포화 이진 트리에서 진행된다. 포화 이진 트리의 각 리프 노드에는 아래 그림과 같이 번호가 $1, \, 2, \, \cdots, 2^{K - 1}$로 연속적으로 부여되어 있다.

  • 게임은 승원이부터 시작하며, 자신의 차례에서 노드를 하나 선택해 그 노드의 서브 트리를 모두 가져간다. 단, 이때 선택한 서브 트리의 리프 노드의 번호는 $[a, \, b]$에 속해야 하며, 일부라도 가져간 부분이 있으면 가져갈 수 없다.
  • 자신의 차례에서 더 이상 선택할 수 있는 노드가 남아있지 않다면, 패배한다.

승원이와 민재는 이 게임의 달인이므로 최선의 전략으로 게임을 한다. 이 때, 민재가 이기게 되는 $(a, \, b)$ 순서쌍의 개수를 구하라. ($1 \leq a \leq b \leq 2^{K - 1}$)

입력

포화 이진 트리의 높이를 나타내는 정수 $K$가 주어진다. ($1 \leq K \leq 2^{18} = 262 \, 144$)

출력

문제의 답을 $998 \, 244 \, 353$으로 나눈 나머지를 출력하라.

서브태스크

번호배점제한
110

$K \leq 2^2 = 4$

220

$K \leq 2^9 = 512$

325

$K \leq 2^{12} = 4 \, 096$

445

추가적인 제약조건 없음

예제 입력 1

3

예제 출력 1

1

민재가 이기는 경우로 가능한 $(a, \, b)$ 순서쌍은 $(2, \, 3)$ 뿐이다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.