#![allow(dead_code, unused_imports, unused_macros, non_snake_case)] use proconio::{ input, input_interactive, marker::{Bytes, Chars, Usize1}, }; fn main() { input! { n: i64, t : usize, k: i64, l : i64, } const MOD: i64 = 998244353; let inv6 = modinv(6, MOD); let mut mat = vec![vec![0; t]; t]; for i in 1..t { mat[i][i - 1] = 1; } mat[0][0] = (k - 1) * inv6 % MOD; mat[0][1] = (l - k) * inv6 % MOD; mat[0][t - 1] = (7 - l) * inv6 % MOD; let res = mat_pow(&mat, n - 1, MOD); println!("{}", res[0][0]); } pub fn modpow(mut x: i64, mut y: i64, modulo: i64) -> i64 { x %= modulo; if x == 0 { return 0; } let mut ret = 1; let mut cur = x; while y > 0 { if y & 1 > 0 { ret = ret * cur % modulo; } cur = cur * cur % modulo; y >>= 1; } ret } pub fn modinv(mut x: i64, modulo: i64) -> i64 { x = x.rem_euclid(modulo); extgcd(x, modulo).0.rem_euclid(modulo) } // return (x, y, gcd(a, b)) s.t. a * x + b * y = gcd(a, b) pub fn extgcd(a: i64, b: i64) -> (i64, i64, i64) { let mut x1 = 1; let mut y1 = 0; let mut m = a; let mut x2 = 0; let mut y2 = 1; let mut n = b; while m % n != 0 { let q = m / n; x1 -= q * x2; y1 -= q * y2; m -= q * n; std::mem::swap(&mut x1, &mut x2); std::mem::swap(&mut y1, &mut y2); std::mem::swap(&mut m, &mut n); } (x2, y2, n) } pub fn mat_mult(a: &[Vec], b: &[Vec], modulo: i64) -> Vec> { let n = a.len(); let m = a[0].len(); assert_eq!(b.len(), m); let o = b[0].len(); let mut res = vec![vec![0; o]; n]; for i in 0..n { for (j, bj) in b.iter().enumerate() { for (k, bjk) in bj.iter().enumerate() { res[i][k] = (res[i][k] + a[i][j] * bjk) % modulo; } } } res } pub fn mat_pow(a: &[Vec], mut k: i64, modulo: i64) -> Vec> { let n = a.len(); assert_eq!(a[0].len(), n); let mut res = vec![vec![0; n]; n]; for (i, resi) in res.iter_mut().enumerate() { resi[i] = 1; } let mut v = a.to_owned(); while k > 0 { if k & 1 == 1 { res = mat_mult(&v, &res, modulo); } v = mat_mult(&v, &v, modulo); k >>= 1; } res }