Counting Valid 0-1 Sequences

We call a binary sequence \(s = s_0s_1\ldots s_{n-1}\) of length \(n\) valid if it satisfies the following condition. Given a positive integer \(k\) and assuming \(2^k \le n\), for every contiguous segment of \(k\) bits, namely for every index \(0 \le i \le n-k\) if we define

[ t = \sum_{j=0}^{k-1} s_{i+j} 2^{k-1-j}, \quad 0 \le t < 2^k, ]

then the bit with index \(t\) (that is, \(s_t\)) must be \(1\). In other words, if we view each length-\(k\) segment of \(s\) as a \(k\)-bit binary number \(t\), then the \(t\)th bit of \(s\) must be \(1\). Your task is to count the number of valid sequences \(s\) of length \(n\). As the answer can be large, output it modulo \(998\,244\,353\).

Note:

• The bits of \(s\) are numbered from \(0\) to \(n-1\).
• When a contiguous segment \(s_i, s_{i+1}, \ldots, s_{i+k-1}\) is interpreted as the binary number \(t\) (with the leftmost bit being the most significant), it must hold that \(s_t = 1\).

It is guaranteed that \(2^k \le n\), so that the index \(t\) is always a valid index of \(s\>.

inputFormat

The input consists of a single line containing two integers \(n\) and \(k\) separated by a space, where \(n\) is the length of the sequence and \(k\) is the length of the contiguous segment to consider.

It is guaranteed that \(2^k \le n\).

outputFormat

Output a single integer, the number of valid \(0-1\) sequences of length \(n\) modulo \(998\,244\,353\).

sample

3 1

3