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$으로 나눈 나머지를 출력하라.