A physical toggle switch emits a binary trace of length N, represented as s[1], s[2], ..., s[N]. A raw flip occurs at gap i (between s[i] and s[i+1] for $1 \le i < N$) if s[i] != s[i+1].

Due to physical bouncing, the switch uses a debounce window of size g. We scan the gaps from left to right (from gap 1 to N - 1) maintaining a lock counter, which is initially 0. For each gap:

• If the lock counter is greater than 0, the current gap is muted. Even if a raw flip occurs at this gap, it is ignored and does not register. The lock counter then decreases by 1.
• If the lock counter is equal to 0 and a raw flip occurs, it registers (counts towards the total registered flips), and the lock counter is set to g - 1.
• If the lock counter is equal to 0 and no raw flip occurs, the lock counter remains 0.

Find the number of valid binary traces of length N that result in exactly K registered flips. Since the count can be large, return the answer modulo 998244353.

Input Format

• The first line contains an integer, N, denoting the length of the binary trace.
• The second line contains an integer, K, denoting the exact number of registered flips required.
• The third line contains an integer, g, denoting the size of the debounce window.

Constraints

• $1 \le N \le 10^5$
• $0 \le K \le N$
• $1 \le g \le N$