34150번 - Game with Segment Tree 2 서브태스크

문제

승원이는 수열과 쿼리 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$으로 나눈 나머지를 출력하라.

제한

서브태스크

힌트