#include #include #include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; using i32 = int32_t; #define REP(i, s, t) for (i32 i = (s); i < (t); ++i) #define PER(i, s, t) for (i32 i = (t)-1; i >= (s); --i) vector fact, ifact, inv; const i32 m = 100000; void init(void) { fact.resize(m + 1, 1); ifact.resize(m + 1, 1); inv.resize(m + 1, 1); REP(i, 1, m + 1) fact.at(i) = i * fact.at(i - 1); ifact.at(m) = fact.at(m).inv(); PER(i, 1, m) { inv.at(i + 1) = ifact.at(i + 1) * fact.at(i); ifact.at(i) = ifact.at(i + 1) * (i + 1); } } i32 read_int(void) { i32 n; cin >> n; return n; } int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); init(); const i32 k = read_int(); const i32 q = read_int(); vector dp(m + 1); dp[0] = 1; mint sum = 1; REP(i, 1, m + 1) { if (i > k) sum -= dp[i - k - 1]; dp[i] = sum * inv[i]; sum += dp[i]; } const i32 batch = 2000; vector> memo; REP(i, 0, m / batch) { vector a(dp.begin(), dp.begin() + i * batch); vector b = convolution(a, dp); if (b.empty()) { b.resize(m + 1); } memo.emplace_back(b); } auto calc = [&](const i32 n, const i32 k) -> mint { assert(k <= n); if (k < 0) return 0; const i32 p = k / batch; mint res = memo[p][n]; REP(i, p * batch, k + 1) res += dp[i] * dp[n - i]; return res; }; REP(i, 0, q) { const i32 n = read_int(); const i32 l = read_int(); const i32 r = read_int(); mint ans = calc(n - 1, r - 1) - calc(n - 1, l - 2); ans *= fact[n - 1]; cout << ans.val() << "\n"; } return 0; }