AtCoder Beginner Contest 425 E

https://atcoder.jp/contests/abc425/tasks/abc425_e

単に

を計算するだけですが、Mが素数とは限らないので割り算ができません。
素数ごとに計算すると簡単です。nの階乗が素数pをいくつ持っているかは、

で計算できます。入力例1の最初のテストだと、4は2を個持っています。3は1個です。2は2を1個、3を0個持っているので、となります。
Cをソートしておくと速くなります。

// Count Sequences 2
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn pow(n: i64, e: u32, d: i64) -> i64 {
    if e == 0 {
        1
    }
    else if e == 1 {
        n
    }
    else if e % 2 == 1 {
        n * pow(n, e-1, d) % d
    }
    else {
        let m = pow(n, e/2, d);
        m * m % d
    }
}


//////////////////// prime ////////////////////

fn make_prime_table(N: usize) -> Vec<i64> {
    let mut a: Vec<bool> = vec![true; N+1];
    for p in (2usize..).take_while(|&p| p*p <= N) {
        if !a[p] {
            continue
        }
        for m in (p*p..N+1).step_by(p) {
            a[m] = false
        }
    }
    (2..N+1).filter(|&n| a[n]).map(|n| n as i64).collect::<Vec<i64>>()
}


//////////////////// Test ////////////////////

struct Test {
    M: i64,
    C: Vec<i64>,
    S: i64,
    primes: Vec<i64>
}

impl Test {
    fn read(M: i64) -> Test {
        let _N: usize = read();
        let mut C: Vec<i64> = read_vec();
        C.sort();
        let S: i64 = C.iter().sum::<i64>();
        let primes = make_prime_table(S as usize);
        Test { M, C, S, primes }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, i64) {
    let v: Vec<i64> = read_vec();
    let (T, M) = (v[0] as usize, v[1]);
    (T, M)
}

fn num_exp(n: i64, p: i64) -> u32 {
    let mut q = p;
    let mut e: u32 = 0;
    while n >= q {
        e += (n / q) as u32;
        q *= p
    }
    e
}

fn F_each(test: Test) -> i64 {
    let mut m: i64 = 1;
    let mut first: usize = 0;
    for &p in test.primes.iter() {
        let mut e: u32 = num_exp(test.S, p);
        for i in first..test.C.len() {
            let e1 = num_exp(test.C[i], p);
            e -= e1;
            if e1 == 0 {
                first = i + 1
            }
        }
        m = m * pow(p, e, test.M) % test.M
    }
    m
}

fn F(T: usize, M: i64) {
    for _ in 0..T {
        let test = Test::read(M);
        println!("{}", F_each(test))
    }
}

fn main() {
    let (T, M) = read_input();
    F(T, M)
}