use modint2::Modint998244353; type Mint = Modint998244353; fn main() { let (n, m, q) = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) }; let aa: Vec<_> = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|x| x.parse::().unwrap() - 1) .collect() }; let lr: Vec<_> = (0..q) .map(|_| { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::().unwrap() - 1, iter.next().unwrap().parse::().unwrap(), ) }) .collect(); let mut acc = vec![Mint::new(0); n + 1]; for (i, &a) in aa.iter().enumerate().rev() { acc[i] = acc[i + 1] + Mint::new(m).pow(n - 1 - i) * a; } for &(l, r) in &lr { let ans = (acc[l] - acc[r]) / Mint::new(m).pow(n - r) + 1; println!("{}", ans); } } pub mod modint2 { //! This module implements modular arithmetic. use std::{ iter::{Product, Sum}, ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign}, }; type InnerType = u32; /// Returns `x` such that `a * x` is equivalent to `1` with `m` as the modulus. fn modinv(a: u32, m: u32) -> u32 { let (mut a, mut b, mut s, mut t) = (a as i64, m as i64, 1, 0); while b != 0 { let q = a / b; a -= q * b; std::mem::swap(&mut a, &mut b); s -= q * t; std::mem::swap(&mut s, &mut t); } assert_eq!( a.abs(), 1, "\ There is no multiplicative inverse of `a` with `m` as the modulus, \ because `a` and `m` are not prime to each other (gcd(a, m) = {}).", a.abs() ); ((s % m as i64 + m as i64) % m as i64) as u32 } pub trait Reminder { /// Returns the remainder divided by `modulus`. fn reminder(self, modulus: InnerType) -> InnerType; } macro_rules! impl_reminder_for_small_unsigned_int { ($($unsigned_small_int: tt), *) => { $( impl Reminder for $unsigned_small_int { fn reminder(self, modulus: InnerType) -> InnerType { self as InnerType % modulus } } )* }; } // Implements `Reminder` trait for `u8`, `u16` and `u32`. impl_reminder_for_small_unsigned_int!(u8, u16, u32); macro_rules! impl_reminder_for_large_unsigned_int { ($($unsigned_large_int: tt), *) => { $( impl Reminder for $unsigned_large_int { fn reminder(self, modulus: InnerType) -> InnerType { (self % modulus as Self) as InnerType } } )* }; } // Implements `Reminder` trait for `usize`, `u64` and `u128`. impl_reminder_for_large_unsigned_int!(usize, u64, u128); macro_rules! impl_reminder_for_small_signed_int { ($($signed_small_int: tt), *) => { $( impl Reminder for $signed_small_int { fn reminder(self, modulus: InnerType) -> InnerType { (self as i32 % modulus as i32 + modulus as i32) as InnerType % modulus } } )* }; } // Implements `Reminder` trait for `i8`, `i16` and `i32`. impl_reminder_for_small_signed_int!(i8, i16, i32); macro_rules! impl_reminder_for_large_signed_int { ($($signed_large_int: tt), *) => { $( impl Reminder for $signed_large_int { fn reminder(self, modulus: InnerType) -> InnerType { (self % modulus as Self + modulus as Self) as InnerType % modulus } } )* }; } // Implements `Reminder` trait for `isize`, `i64` and `i128`. impl_reminder_for_large_signed_int!(isize, i64, i128); /// Structure for modular arithmetic. #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] pub struct Modint { rem: InnerType, } impl std::fmt::Display for Modint { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.rem) } } impl Default for Modint { /// Returns a `Modint` instance equivalent to `0`. fn default() -> Self { Self::raw(0) } } impl From for Modint where T: Reminder, { fn from(value: T) -> Self { Self::new(value) } } impl Add> for Modint { type Output = Self; fn add(self, rhs: Modint) -> Self::Output { Self::raw((self.rem + rhs.rem) % MODULUS) } } impl Sub> for Modint { type Output = Self; fn sub(self, rhs: Modint) -> Self::Output { Self::raw((self.rem + MODULUS - rhs.rem) % MODULUS) } } impl Mul> for Modint { type Output = Self; fn mul(self, rhs: Modint) -> Self::Output { Self::raw((self.rem as u64 * rhs.rem as u64 % MODULUS as u64) as InnerType) } } impl Div> for Modint { type Output = Self; #[allow(clippy::suspicious_arithmetic_impl)] fn div(self, rhs: Modint) -> Self::Output { self * rhs.inv() } } impl Neg for Modint { type Output = Self; fn neg(self) -> Self::Output { Self::raw((MODULUS - self.rem) % MODULUS) } } impl AddAssign> for Modint { fn add_assign(&mut self, rhs: Modint) { *self = *self + rhs; } } impl SubAssign> for Modint { fn sub_assign(&mut self, rhs: Modint) { *self = *self - rhs; } } impl MulAssign> for Modint { fn mul_assign(&mut self, rhs: Modint) { *self = *self * rhs; } } impl DivAssign> for Modint { fn div_assign(&mut self, rhs: Modint) { *self = *self / rhs; } } impl Add for Modint where T: Reminder, { type Output = Modint; fn add(self, rhs: T) -> Self::Output { self + Self::new(rhs) } } impl Sub for Modint where T: Reminder, { type Output = Modint; fn sub(self, rhs: T) -> Self::Output { self - Self::new(rhs) } } impl Mul for Modint where T: Reminder, { type Output = Modint; fn mul(self, rhs: T) -> Self::Output { self * Self::new(rhs) } } impl Div for Modint where T: Reminder, { type Output = Modint; fn div(self, rhs: T) -> Self::Output { self / Self::new(rhs) } } impl AddAssign for Modint where T: Reminder, { fn add_assign(&mut self, rhs: T) { *self += Modint::new(rhs); } } impl SubAssign for Modint where T: Reminder, { fn sub_assign(&mut self, rhs: T) { *self -= Modint::new(rhs); } } impl MulAssign for Modint where T: Reminder, { fn mul_assign(&mut self, rhs: T) { *self *= Modint::new(rhs); } } impl DivAssign for Modint where T: Reminder, { fn div_assign(&mut self, rhs: T) { *self /= Modint::new(rhs); } } impl Sum> for Modint { fn sum>>(iter: I) -> Self { iter.fold(Self::new(0), |acc, x| acc + x) } } impl<'a, const MODULUS: InnerType> Sum<&'a Modint> for Modint { fn sum>>(iter: I) -> Self { iter.fold(Self::new(0), |acc, &x| acc + x) } } impl Product> for Modint { fn product>>(iter: I) -> Self { iter.fold(Self::new(1), |acc, x| acc * x) } } impl<'a, const MODULUS: InnerType> Product<&'a Modint> for Modint { fn product>>(iter: I) -> Self { iter.fold(Self::new(1), |acc, &x| acc * x) } } impl Modint { /// Returns the modulus. pub fn modulus() -> InnerType { MODULUS } /// Returns a `Modint` instance equivalent to `a`. pub fn new(a: T) -> Self where T: Reminder, { Self { rem: a.reminder(MODULUS), } } /// Creates a `Modint` instance from a non-negative integer less than `MODULUS`. pub fn raw(a: InnerType) -> Self { Self { rem: a } } /// Returns `x` such that `x * q` is equivalent to `p`. pub fn frac(p: T, q: T) -> Self where T: Reminder, { Self::new(p) / Self::new(q) } /// Returns the remainder divided by `MODULUS`. /// The returned value is a non-negative integer less than `MODULUS`. pub fn rem(self) -> InnerType { self.rem } /// Returns the modular multiplicative inverse. pub fn inv(self) -> Self { Self { rem: modinv(self.rem, MODULUS), } } /// Calculates the power of `exp` using the iterative squaring method. pub fn pow(self, exp: T) -> Self where T: ToExponent, { let mut ret = Self::new(1); let mut mul = self; let exp = exp.to_exponent(); let mut t = exp.abs; while t != 0 { if t & 1 == 1 { ret *= mul; } mul *= mul; t >>= 1; } if exp.neg { ret = ret.inv(); } ret } } pub struct Exponent { neg: bool, abs: u128, } pub trait ToExponent { fn to_exponent(self) -> Exponent; } macro_rules! impl_to_exponent_for_unsigned_int { ($($ty: tt), *) => { $( impl ToExponent for $ty { fn to_exponent(self) -> Exponent { Exponent { neg: false, abs: self as u128, } } } )* }; } impl_to_exponent_for_unsigned_int!(usize, u8, u16, u32, u64, u128); macro_rules! impl_to_exponent_for_signed_int { ($($ty: tt), *) => { $( impl ToExponent for $ty { fn to_exponent(self) -> Exponent { Exponent { neg: self.is_negative(), abs: self.abs() as u128, } } } )* }; } impl_to_exponent_for_signed_int!(isize, i8, i16, i32, i64, i128); #[derive(Debug, Clone)] pub struct Factorial { /// Upper limit of available factorial argument. upper_limit: usize, /// List of factorials. fac: Vec, /// List of factorial inverses. inv_fac: Vec, } impl Factorial> { /// Calculates factorial and its inverse for non-negative integers bellow `upper_limit`. pub fn new(upper_limit: usize) -> Self { let mut fac = vec![Modint::new(1); upper_limit + 1]; for i in 0..upper_limit { fac[i + 1] = fac[i] * (i + 1); } let mut inv_fac = vec![fac[upper_limit].inv(); upper_limit + 1]; for i in (0..upper_limit).rev() { inv_fac[i] = inv_fac[i + 1] * (i + 1); } Self { upper_limit, fac, inv_fac, } } /// Returns the factorial `n`. pub fn factorial(&self, n: usize) -> Modint { assert!( n <= self.upper_limit, "The maximum number of available factorial arguments has been exceeded." ); self.fac[n] } /// Returns the inverse of the factorial of `n`. pub fn inverse_factorial(&self, n: usize) -> Modint { assert!( n <= self.upper_limit, "The maximum number of available factorial arguments has been exceeded." ); self.inv_fac[n] } /// Calculates the number of ways to select and arrange `k` objects from `n` unique objects. pub fn permutations(&self, n: usize, k: usize) -> Modint { if n >= k { self.factorial(n) * self.inverse_factorial(n - k) } else { Modint::new(0) } } /// Calculates the number of ways to select `k` objects from `n` unique objects. pub fn combinations(&self, n: usize, k: usize) -> Modint { if n >= k { self.factorial(n) * self.inverse_factorial(n - k) * self.inverse_factorial(k) } else { Modint::new(0) } } /// Calculates the number of ways to select `k` objects from `n` unique objects, allowing for duplicates. pub fn combinations_with_repetition(&self, n: usize, k: usize) -> Modint { if n == 0 { return if k == 0 { Modint::new(1) } else { Modint::new(0) }; } self.combinations(n + k - 1, k) } } /// The type `Modint` with 1000000007 as the modulus. pub type Modint1000000007 = Modint<1000000007>; /// The type `Modint` with 998244353 as the modulus. pub type Modint998244353 = Modint<998244353>; }