빈 수정

$N$개의 수정이 한 줄로 놓여 있다. 그중 일부는 허상일 수 있다.

준은 $1 \le l \le r \le N$을 만족하는 모든 쌍 $(l, r)$에 대해, $l$번째부터 $r$번째까지의 구간(양 끝 포함)에 있는 진짜 수정의 개수를 세고 그 개수가 짝수인지 홀수인지 기록했다.

기록된 $\frac{N(N+1)}{2}$개의 결과를 보면, 진짜 수정의 개수가 홀수인 구간이 $k$개 있었다. 가능한 수정의 배열은 몇 가지인가? 답을 $998244353$으로 나눈 나머지를 구하라.

왼쪽에서 $i$번째 수정이 한 배열에서는 진짜이고 다른 배열에서는 허상이면, 두 배열은 서로 다른 것으로 본다.

$T$개의 문제가 주어진다. 각각에 답하라.

첫 줄에 $T$가 주어진다. 다음 $T$개의 줄에 각각 $N_i$와 $K_i$가 주어진다.

$T$개의 줄을 출력한다. $i$번째 줄에는 $N = N_i$, $K = K_i$일 때의 답을 출력한다.

실제 수정을 1, 허상을 0으로 나타내면, $N = 3$, $K = 4$일 때 조건을 만족하는 배열은 다음 세 가지이다.

• 0, 1, 0
• 1, 0, 1
• 1, 1, 1