Constrained Binary Sequence

Given three integers n, k and a. Consider a binary (0-1) sequence of length n. It is required that for every contiguous substring of length k the number of zeros is either exactly a or exactly a+1 (i.e. the count of 0's in that substring is either \(a\) or \(a+1\)).

Find the number of sequences satisfying the condition above. Since the answer can be very large, output it modulo \(998244353\).

Observation and Hint: If we denote by \(C(k, r)\) the binomial coefficient, then one may prove that the answer is given by

[ \Bigl(C(k,a)+C(k,a+1)\Bigr)\cdot3^{n-k} \pmod{998244353}. ]

This is because the first window (the first k bits) can have either \(a\) or \(a+1\) zeros, and each subsequent bit (from position k+1 to n) admits exactly 3 possibilities (depending on the overlapping window transition) while maintaining the required condition.

inputFormat

The input consists of a single line containing three integers n, k and a.

outputFormat

Output a single integer, the number of valid sequences modulo 998244353.

sample

3 3 1

6