#976868 (Rust) No.502 階乗を計算するだけ

• 問題: No.502 階乗を計算するだけ
• ユーザー: atcoder8
• 提出日時: 2024-04-23 16:29:08
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 5 ms / 1,000 ms
• コード長: 26,534 bytes
• コンパイル時間: 1,184 ms
• コンパイル使用メモリ: 166,784 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-23 16:29:11
• 合計ジャッジ時間: 2,604 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	0 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	0 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	0 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	1 ms; 5,376 KB
testcase_22	AC	4 ms; 5,376 KB
testcase_23	AC	2 ms; 5,376 KB
testcase_24	AC	3 ms; 5,376 KB
testcase_25	AC	1 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB
testcase_29	AC	1 ms; 5,376 KB
testcase_30	AC	4 ms; 5,376 KB
testcase_31	AC	3 ms; 5,376 KB
testcase_32	AC	1 ms; 5,376 KB
testcase_33	AC	5 ms; 5,376 KB
testcase_34	AC	2 ms; 5,376 KB
testcase_35	AC	4 ms; 5,376 KB
testcase_36	AC	1 ms; 5,376 KB
testcase_37	AC	4 ms; 5,376 KB
testcase_38	AC	2 ms; 5,376 KB
testcase_39	AC	4 ms; 5,376 KB
testcase_40	AC	3 ms; 5,376 KB
testcase_41	AC	1 ms; 5,376 KB
testcase_42	AC	1 ms; 5,376 KB
testcase_43	AC	1 ms; 5,376 KB
testcase_44	AC	1 ms; 5,376 KB
testcase_45	AC	0 ms; 5,376 KB
testcase_46	AC	1 ms; 5,376 KB
testcase_47	AC	0 ms; 5,376 KB
testcase_48	AC	1 ms; 5,376 KB
testcase_49	AC	1 ms; 5,376 KB
testcase_50	AC	1 ms; 5,376 KB
testcase_51	AC	1 ms; 5,376 KB

ソースコード

use modint2::Modint1000000007;
use proconio::input;

type Mint = Modint1000000007;

const INTERVAL: usize = 10_usize.pow(6);

fn main() {
    println!("{}", solve());
}

fn solve() -> Mint {
    input! {
        n: usize,
    }

    if n >= 1000000007 {
        return Mint::new(0);
    }

    let mut fac = Mint::new(FACTORIALS[n / INTERVAL]);
    for i in n / INTERVAL * INTERVAL + 1..=n {
        fac *= i;
    }

    fac
}

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<const MODULUS: InnerType> {
        rem: InnerType,
    }

    impl<const MODULUS: InnerType> std::fmt::Display for Modint<MODULUS> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.rem)
        }
    }

    impl<const MODULUS: InnerType> Default for Modint<MODULUS> {
        /// Returns a `Modint` instance equivalent to `0`.
        fn default() -> Self {
            Self::raw(0)
        }
    }

    impl<T, const MODULUS: InnerType> From<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        fn from(value: T) -> Self {
            Self::new(value)
        }
    }

    impl<const MODULUS: InnerType> Add<Modint<MODULUS>> for Modint<MODULUS> {
        type Output = Self;

        fn add(self, rhs: Modint<MODULUS>) -> Self::Output {
            Self::raw((self.rem + rhs.rem) % MODULUS)
        }
    }

    impl<const MODULUS: InnerType> Sub<Modint<MODULUS>> for Modint<MODULUS> {
        type Output = Self;

        fn sub(self, rhs: Modint<MODULUS>) -> Self::Output {
            Self::raw((self.rem + MODULUS - rhs.rem) % MODULUS)
        }
    }

    impl<const MODULUS: InnerType> Mul<Modint<MODULUS>> for Modint<MODULUS> {
        type Output = Self;

        fn mul(self, rhs: Modint<MODULUS>) -> Self::Output {
            Self::raw((self.rem as u64 * rhs.rem as u64 % MODULUS as u64) as InnerType)
        }
    }

    impl<const MODULUS: InnerType> Div<Modint<MODULUS>> for Modint<MODULUS> {
        type Output = Self;

        #[allow(clippy::suspicious_arithmetic_impl)]
        fn div(self, rhs: Modint<MODULUS>) -> Self::Output {
            self * rhs.inv()
        }
    }

    impl<const MODULUS: InnerType> Neg for Modint<MODULUS> {
        type Output = Self;

        fn neg(self) -> Self::Output {
            Self::raw((MODULUS - self.rem) % MODULUS)
        }
    }

    impl<const MODULUS: InnerType> AddAssign<Modint<MODULUS>> for Modint<MODULUS> {
        fn add_assign(&mut self, rhs: Modint<MODULUS>) {
            *self = *self + rhs;
        }
    }

    impl<const MODULUS: InnerType> SubAssign<Modint<MODULUS>> for Modint<MODULUS> {
        fn sub_assign(&mut self, rhs: Modint<MODULUS>) {
            *self = *self - rhs;
        }
    }

    impl<const MODULUS: InnerType> MulAssign<Modint<MODULUS>> for Modint<MODULUS> {
        fn mul_assign(&mut self, rhs: Modint<MODULUS>) {
            *self = *self * rhs;
        }
    }

    impl<const MODULUS: InnerType> DivAssign<Modint<MODULUS>> for Modint<MODULUS> {
        fn div_assign(&mut self, rhs: Modint<MODULUS>) {
            *self = *self / rhs;
        }
    }

    impl<const MODULUS: InnerType, T> Add<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        type Output = Modint<MODULUS>;

        fn add(self, rhs: T) -> Self::Output {
            self + Self::new(rhs)
        }
    }

    impl<const MODULUS: InnerType, T> Sub<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        type Output = Modint<MODULUS>;

        fn sub(self, rhs: T) -> Self::Output {
            self - Self::new(rhs)
        }
    }

    impl<const MODULUS: InnerType, T> Mul<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        type Output = Modint<MODULUS>;

        fn mul(self, rhs: T) -> Self::Output {
            self * Self::new(rhs)
        }
    }

    impl<const MODULUS: InnerType, T> Div<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        type Output = Modint<MODULUS>;

        fn div(self, rhs: T) -> Self::Output {
            self / Self::new(rhs)
        }
    }

    impl<const MODULUS: InnerType, T> AddAssign<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        fn add_assign(&mut self, rhs: T) {
            *self += Modint::new(rhs);
        }
    }

    impl<const MODULUS: InnerType, T> SubAssign<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        fn sub_assign(&mut self, rhs: T) {
            *self -= Modint::new(rhs);
        }
    }

    impl<const MODULUS: InnerType, T> MulAssign<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        fn mul_assign(&mut self, rhs: T) {
            *self *= Modint::new(rhs);
        }
    }

    impl<const MODULUS: InnerType, T> DivAssign<T> for Modint<MODULUS>
    where
        T: Reminder,
    {
        fn div_assign(&mut self, rhs: T) {
            *self /= Modint::new(rhs);
        }
    }

    impl<const MODULUS: InnerType> Sum<Modint<MODULUS>> for Modint<MODULUS> {
        fn sum<I: Iterator<Item = Modint<MODULUS>>>(iter: I) -> Self {
            iter.fold(Self::new(0), |acc, x| acc + x)
        }
    }

    impl<'a, const MODULUS: InnerType> Sum<&'a Modint<MODULUS>> for Modint<MODULUS> {
        fn sum<I: Iterator<Item = &'a Modint<MODULUS>>>(iter: I) -> Self {
            iter.fold(Self::new(0), |acc, &x| acc + x)
        }
    }

    impl<const MODULUS: InnerType> Product<Modint<MODULUS>> for Modint<MODULUS> {
        fn product<I: Iterator<Item = Modint<MODULUS>>>(iter: I) -> Self {
            iter.fold(Self::new(1), |acc, x| acc * x)
        }
    }

    impl<'a, const MODULUS: InnerType> Product<&'a Modint<MODULUS>> for Modint<MODULUS> {
        fn product<I: Iterator<Item = &'a Modint<MODULUS>>>(iter: I) -> Self {
            iter.fold(Self::new(1), |acc, &x| acc * x)
        }
    }

    impl<const MODULUS: InnerType> Modint<MODULUS> {
        /// Returns the modulus.
        pub fn modulus() -> InnerType {
            MODULUS
        }

        /// Returns a `Modint` instance equivalent to `a`.
        pub fn new<T>(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 }
        }

        /// Set the remainder of `Modint` instance to `a`.
        pub fn set_rem<T>(&mut self, a: T)
        where
            T: Reminder,
        {
            self.rem = a.reminder(MODULUS);
        }

        /// Returns `x` such that `x * q` is equivalent to `p`.
        pub fn frac<T>(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<T>(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<Modint> {
        /// Upper limit of available factorial argument.
        upper_limit: usize,

        /// List of factorials.
        fac: Vec<Modint>,

        /// List of factorial inverses.
        inv_fac: Vec<Modint>,
    }

    impl<const MODULUS: InnerType> Factorial<Modint<MODULUS>> {
        /// 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<MODULUS> {
            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<MODULUS> {
            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<MODULUS> {
            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<MODULUS> {
            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<MODULUS> {
            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>;
}

const FACTORIALS: [usize; 1001] = [
    1, 641102369, 578095319, 5832229, 259081142, 974067448, 316220877, 690120224, 251368199,
    980250487, 682498929, 134623568, 95936601, 933097914, 167332441, 598816162, 336060741,
    248744620, 626497524, 288843364, 491101308, 245341950, 565768255, 246899319, 968999, 586350670,
    638587686, 881746146, 19426633, 850500036, 76479948, 268124147, 842267748, 886294336,
    485348706, 463847391, 544075857, 898187927, 798967520, 82926604, 723816384, 156530778,
    721996174, 299085602, 323604647, 172827403, 398699886, 530389102, 294587621, 813805606,
    67347853, 497478507, 196447201, 722054885, 228338256, 407719831, 762479457, 746536789,
    811667359, 778773518, 27368307, 438371670, 59469516, 5974669, 766196482, 606322308, 86609485,
    889750731, 340941507, 371263376, 625544428, 788878910, 808412394, 996952918, 585237443,
    1669644, 361786913, 480748381, 595143852, 837229828, 199888908, 526807168, 579691190,
    145404005, 459188207, 534491822, 439729802, 840398449, 899297830, 235861787, 888050723,
    656116726, 736550105, 440902696, 85990869, 884343068, 56305184, 973478770, 168891766,
    804805577, 927880474, 876297919, 934814019, 676405347, 567277637, 112249297, 44930135,
    39417871, 47401357, 108819476, 281863274, 60168088, 692636218, 432775082, 14235602, 770511792,
    400295761, 697066277, 421835306, 220108638, 661224977, 261799937, 168203998, 802214249,
    544064410, 935080803, 583967898, 211768084, 751231582, 972424306, 623534362, 335160196,
    243276029, 554749550, 60050552, 797848181, 395891998, 172428290, 159554990, 887420150,
    970055531, 250388809, 487998999, 856259313, 82104855, 232253360, 513365505, 244109365, 1559745,
    695345956, 261384175, 849009131, 323214113, 747664143, 444090941, 659224434, 80729842,
    570033864, 664989237, 827348878, 195888993, 576798521, 457882808, 731551699, 212938473,
    509096183, 827544702, 678320208, 677711203, 289752035, 66404266, 555972231, 195290384,
    97136305, 349551356, 785113347, 83489485, 66247239, 52167191, 307390891, 547665832, 143066173,
    350016754, 917404120, 296269301, 996122673, 23015220, 602139210, 748566338, 187348575,
    109838563, 574053420, 105574531, 304173654, 542432219, 34538816, 325636655, 437843114,
    630621321, 26853683, 933245637, 616368450, 238971581, 511371690, 557301633, 911398531,
    848952161, 958992544, 925152039, 914456118, 724691727, 636817583, 238087006, 946237212,
    910291942, 114985663, 492237273, 450387329, 834860913, 763017204, 368925948, 475812562,
    740594930, 45060610, 806047532, 464456846, 172115341, 75307702, 116261993, 562519302,
    268838846, 173784895, 243624360, 61570384, 481661251, 938269070, 95182730, 91068149, 115435332,
    495022305, 136026497, 506496856, 710729672, 113570024, 366384665, 564758715, 270239666,
    277118392, 79874094, 702807165, 112390913, 730341625, 103056890, 677948390, 339464594,
    167240465, 108312174, 839079953, 479334442, 271788964, 135498044, 277717575, 591048681,
    811637561, 353339603, 889410460, 839849206, 192345193, 736265527, 316439118, 217544623,
    788132977, 618898635, 183011467, 380858207, 996097969, 898554793, 335353644, 54062950,
    611251733, 419363534, 965429853, 160398980, 151319402, 990918946, 607730875, 450718279,
    173539388, 648991369, 970937898, 500780548, 780122909, 39052406, 276894233, 460373282,
    651081062, 461415770, 358700839, 643638805, 560006119, 668123525, 686692315, 673464765,
    957633609, 199866123, 563432246, 841799766, 385330357, 504962686, 954061253, 128487469,
    685707545, 299172297, 717975101, 577786541, 318951960, 773206631, 306832604, 204355779,
    573592106, 30977140, 450398100, 363172638, 258379324, 472935553, 93940075, 587220627,
    776264326, 793270300, 291733496, 522049725, 579995261, 335416359, 142946099, 472012302,
    559947225, 332139472, 499377092, 464599136, 164752359, 309058615, 86117128, 580204973,
    563781682, 954840109, 624577416, 895609896, 888287558, 836813268, 926036911, 386027524,
    184419613, 724205533, 403351886, 715247054, 716986954, 830567832, 383388563, 68409439, 6734065,
    189239124, 68322490, 943653305, 405755338, 811056092, 179518046, 825132993, 343807435,
    985084650, 868553027, 148528617, 160684257, 882148737, 591915968, 701445829, 529726489,
    302177126, 974886682, 241107368, 798830099, 940567523, 11633075, 325334066, 346091869,
    115312728, 473718967, 218129285, 878471898, 180002392, 699739374, 917084264, 856859395,
    435327356, 808651347, 421623838, 105419548, 59883031, 322487421, 79716267, 715317963,
    429277690, 398078032, 316486674, 384843585, 940338439, 937409008, 940524812, 947549662,
    833550543, 593524514, 996164327, 987314628, 697611981, 636177449, 274192146, 418537348,
    925347821, 952831975, 893732627, 1277567, 358655417, 141866945, 581830879, 987597705,
    347046911, 775305697, 125354499, 951540811, 247662371, 343043237, 568392357, 997474832,
    209244402, 380480118, 149586983, 392838702, 309134554, 990779998, 263053337, 325362513,
    780072518, 551028176, 990826116, 989944961, 155569943, 596737944, 711553356, 268844715,
    451373308, 379404150, 462639908, 961812918, 654611901, 382776490, 41815820, 843321396,
    675258797, 845583555, 934281721, 741114145, 275105629, 666247477, 325912072, 526131620,
    252551589, 432030917, 554917439, 818036959, 754363835, 795190182, 909210595, 278704903,
    719566487, 628514947, 424989675, 321685608, 50590510, 832069712, 198768464, 702004730,
    99199382, 707469729, 747407118, 302020341, 497196934, 5003231, 726997875, 382617671, 296229203,
    183888367, 703397904, 552133875, 732868367, 350095207, 26031303, 863250534, 216665960,
    561745549, 352946234, 784139777, 733333339, 503105966, 459878625, 803187381, 16634739,
    180898306, 68718097, 985594252, 404206040, 749724532, 97830135, 611751357, 31131935, 662741752,
    864326453, 864869025, 167831173, 559214642, 718498895, 91352335, 608823837, 473379392,
    385388084, 152267158, 681756977, 46819124, 313132653, 56547945, 442795120, 796616594,
    256141983, 152028387, 636578562, 385377759, 553033642, 491415383, 919273670, 996049638,
    326686486, 160150665, 141827977, 540818053, 693305776, 593938674, 186576440, 688809790,
    565456578, 749296077, 519397500, 551096742, 696628828, 775025061, 370732451, 164246193,
    915265013, 457469634, 923043932, 912368644, 777901604, 464118005, 637939935, 956856710,
    490676632, 453019482, 462528877, 502297454, 798895521, 100498586, 699767918, 849974789,
    811575797, 438952959, 606870929, 907720182, 179111720, 48053248, 508038818, 811944661,
    752550134, 401382061, 848924691, 764368449, 34629406, 529840945, 435904287, 26011548,
    208184231, 446477394, 206330671, 366033520, 131772368, 185646898, 648711554, 472759660,
    523696723, 271198437, 25058942, 859369491, 817928963, 330711333, 724464507, 437605233,
    701453022, 626663115, 281230685, 510650790, 596949867, 295726547, 303076380, 465070856,
    272814771, 538771609, 48824684, 951279549, 939889684, 564188856, 48527183, 201307702,
    484458461, 861754542, 326159309, 181594759, 668422905, 286273596, 965656187, 44135644,
    359960756, 936229527, 407934361, 267193060, 456152084, 459116722, 124804049, 262322489,
    920251227, 816929577, 483924582, 151834896, 167087470, 490222511, 903466878, 361583925,
    368114731, 339383292, 388728584, 218107212, 249153339, 909458706, 322908524, 202649964,
    92255682, 573074791, 15570863, 94331513, 744158074, 196345098, 334326205, 9416035, 98349682,
    882121662, 769795511, 231988936, 888146074, 137603545, 582627184, 407518072, 919419361,
    909433461, 986708498, 310317874, 373745190, 263645931, 256853930, 876379959, 702823274,
    147050765, 308186532, 175504139, 180350107, 797736554, 606241871, 384547635, 273712630,
    586444655, 682189174, 666493603, 946867127, 819114541, 502371023, 261970285, 825871994,
    126925175, 701506133, 314738056, 341779962, 561011609, 815463367, 46765164, 49187570,
    188054995, 957939114, 64814326, 933376898, 329837066, 338121343, 765215899, 869630152,
    978119194, 632627667, 975266085, 435887178, 282092463, 129621197, 758245605, 827722926,
    201339230, 918513230, 322096036, 547838438, 985546115, 852304035, 593090119, 689189630,
    555842733, 567033437, 469928208, 212842957, 117842065, 404149413, 155133422, 663307737,
    208761293, 206282795, 717946122, 488906585, 414236650, 280700600, 962670136, 534279149,
    214569244, 375297772, 811053196, 922377372, 289594327, 219932130, 211487466, 701050258,
    398782410, 863002719, 27236531, 217598709, 375472836, 810551911, 178598958, 247844667,
    676526196, 812283640, 863066876, 857241854, 113917835, 624148346, 726089763, 564827277,
    826300950, 478982047, 439411911, 454039189, 633292726, 48562889, 802100365, 671734977,
    945204804, 508831870, 398781902, 897162044, 644050694, 892168027, 828883117, 277714559,
    713448377, 624500515, 590098114, 808691930, 514359662, 895205045, 715264908, 628829100,
    484492064, 919717789, 513196123, 748510389, 403652653, 574455974, 77123823, 172096141,
    819801784, 581418893, 15655126, 15391652, 875641535, 203191898, 264582598, 880691101,
    907800444, 986598821, 340030191, 264688936, 369832433, 785804644, 842065079, 423951674,
    663560047, 696623384, 496709826, 161960209, 331910086, 541120825, 951524114, 841656666,
    162683802, 629786193, 190395535, 269571439, 832671304, 76770272, 341080135, 421943723,
    494210290, 751040886, 317076664, 672850561, 72482816, 493689107, 135625240, 100228913,
    684748812, 639655136, 906233141, 929893103, 277813439, 814362881, 562608724, 406024012,
    885537778, 10065330, 60625018, 983737173, 60517502, 551060742, 804930491, 823845496, 727416538,
    946421040, 678171399, 842203531, 175638827, 894247956, 538609927, 885362182, 946464959,
    116667533, 749816133, 241427979, 871117927, 281804989, 163928347, 563796647, 640266394,
    774625892, 59342705, 256473217, 674115061, 918860977, 322633051, 753513874, 393556719,
    304644842, 767372800, 161362528, 754787150, 627655552, 677395736, 799289297, 846650652,
    816701166, 687265514, 787113234, 358757251, 701220427, 607715125, 245795606, 600624983,
    10475577, 728620948, 759404319, 36292292, 491466901, 22556579, 114495791, 647630109, 586445753,
    482254337, 718623833, 763514207, 66547751, 953634340, 351472920, 308474522, 494166907,
    634359666, 172114298, 865440961, 364380585, 921648059, 965683742, 260466949, 117483873,
    962540888, 237120480, 620531822, 193781724, 213092254, 107141741, 602742426, 793307102,
    756154604, 236455213, 362928234, 14162538, 753042874, 778983779, 25977209, 49389215, 698308420,
    859637374, 49031023, 713258160, 737331920, 923333660, 804861409, 83868974, 682873215,
    217298111, 883278906, 176966527, 954913, 105359006, 390019735, 10430738, 706334445, 315103615,
    567473423, 708233401, 48160594, 946149627, 346966053, 281329488, 462880311, 31503476,
    185438078, 965785236, 992656683, 916291845, 881482632, 899946391, 321900901, 512634493,
    303338827, 121000338, 967284733, 492741665, 152233223, 165393390, 680128316, 917041303,
    532702135, 741626808, 496442755, 536841269, 131384366, 377329025, 301196854, 859917803,
    676511002, 373451745, 847645126, 823495900, 576368335, 73146164, 954958912, 847549272,
    241289571, 646654592, 216046746, 205951465, 3258987, 780882948, 822439091, 598245292,
    869544707, 698611116,
];