from collections import * import sys import heapq import bisect import itertools from functools import lru_cache from types import GeneratorType from fractions import Fraction import math import copy import random # sys.setrecursionlimit(int(1e7)) # @lru_cache(maxsize=None) # CPython特化 # @bootstrap # PyPy特化(こっちのほうが速い) yield dfs(), yield Noneを忘れずに def bootstrap(f, stack=[]): # yield def wrappedfunc(*args, **kwargs): if stack: return f(*args, **kwargs) else: to = f(*args, **kwargs) while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to return wrappedfunc dxdy1 = ((0, 1), (0, -1), (1, 0), (-1, 0)) # 上下右左 dxdy2 = ( (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1), ) # 8方向すべて dxdy3 = ((0, 1), (1, 0)) # 右 or 下 dxdy4 = ((1, 1), (1, -1), (-1, 1), (-1, -1)) # 斜め INF = float("inf") _INF = 1 << 60 MOD = 998244353 mod = 998244353 MOD2 = 10**9 + 7 mod2 = 10**9 + 7 # memo : len([a,b,...,z])==26 # memo : 2^20 >= 10^6 # 小数の計算を避ける : x/y -> (x*big)//y ex:big=10**9 # @:小さい文字, ~:大きい文字,None: 空の文字列 # ユークリッドの互除法:gcd(x,y)=gcd(x,y-x) # memo : d 桁以下の p 進表記を用いると p^d-1 以下のすべての # 非負整数を表現することができる # memo : (X,Y) -> (X+Y,X−Y) <=> 点を原点を中心に45度回転し、√2倍に拡大 # memo : (x,y)のx正から見た偏角をラジアンで(-πからπ]: math.atan2(y, x) # memo : a < bのとき ⌊a⌋ ≦ ⌊b⌋ input = lambda: sys.stdin.readline().rstrip() mi = lambda: map(int, input().split()) li = lambda: list(mi()) ii = lambda: int(input()) py = lambda: print("Yes") pn = lambda: print("No") pf = lambda: print("First") ps = lambda: print("Second") # ACLのではない。機能は減るが、こっちのほうが早い class LazySegTree: def __init__(self, v, op, e, mapping, composition, id_): n = len(v) self._op = op self._e = e self._mapping = mapping self._composition = composition self._id = id_ self._size = 1 << (n - 1).bit_length() self._d = [e] * (2 * self._size) self._lz = [id_] * 2 * self._size for i in range(n): self._d[self._size + i] = v[i] for i in range(self._size - 1, 0, -1): self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1]) def _gindex(self, l, r): l += self._size r += self._size lm = l >> (l & -l).bit_length() rm = r >> (r & -r).bit_length() while r > l: if l <= lm: yield l if r <= rm: yield r l >>= 1 r >>= 1 while l: yield l l >>= 1 def _propagates(self, *ids): for i in reversed(ids): f = self._lz[i] self._lz[i] = self._id self._lz[2 * i] = self._composition(f, self._lz[2 * i]) self._lz[2 * i + 1] = self._composition(f, self._lz[2 * i + 1]) self._d[2 * i] = self._mapping(f, self._d[2 * i]) self._d[2 * i + 1] = self._mapping(f, self._d[2 * i + 1]) def apply(self, l, r, f): (*ids,) = self._gindex(l, r) self._propagates(*ids) l += self._size r += self._size while l < r: if l & 1: self._lz[l] = self._composition(f, self._lz[l]) self._d[l] = self._mapping(f, self._d[l]) l += 1 if r & 1: self._lz[r - 1] = self._composition(f, self._lz[r - 1]) self._d[r - 1] = self._mapping(f, self._d[r - 1]) l >>= 1 r >>= 1 for i in ids: self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1]) def prod(self, l, r): self._propagates(*self._gindex(l, r)) resl = self._e resr = self._e l += self._size r += self._size while l < r: if l & 1: resl = self._op(resl, self._d[l]) l += 1 if r & 1: resr = self._op(self._d[r - 1], resr) l >>= 1 r >>= 1 return self._op(resl, resr) # RMQのとき def op(a, b): return (a + b) % MOD def mapping(f, x): # 更新(dataに作用, fは上書きフラグ(f==ID: False)) return (f + x) % MOD def composition( f, g ): # 更新(lazyに作用, fは上書きフラグ(f==ID: False), 作用順はg→f, fは新しく入ってきたやつ) return (f + g) % MOD ini = 0 ID = ini e = ini N, K = mi() dp = LazySegTree([ini] * (N + 1), op, e, mapping, composition, ID) dp.apply(0, 1, 1) for i in range(N): if i + K <= N: dp.apply(i + K, N + 1, dp.prod(i, i + 1)) print(dp.prod(0, N + 1))