Kortit II

use std::cell::RefCell;
use std::io;
use std::rc::Rc;

const MOD: u128 = 10u128.pow(9) + 7;

fn main() {
    let stdin = io::stdin();

    let cache: Rc<RefCell<Cache>> = Rc::new(RefCell::new(Cache {
        point_data: vec![
            vec![1],
            vec![0, 1],
            vec![0, 1, 7],
            vec![0, 1, 21, 161],
            vec![0, 1, 51, 813, 7631],
            vec![0, 1, 113, 3361, 53833, 607009],
            vec![0, 1, 239, 12421, 320107, 5494017, 72605303],
            vec![0, 1, 493, 42865, 1704693, 42924113, 802028813, 3582337729],
            vec![0, 1, 1003, 141549, 8422679, 302458313, 3494885555, 4134309781, 3919905439],
            vec![0, 1, 2025, 453905, 39474449, 1977056433, 47564649, 187155009, 408347281, 974199489],
            vec![0, 1, 4071, 1426725, 178065811, 3628647969, 1803204639, 2923296653, 1321641563, 3564658313, 3903610631],
            vec![0, 1, 8165, 4422913, 780889437, 3634207041, 1479690389, 2969640273, 1369234749, 3535220017],
            vec![0, 1, 16355, 13579309, 3352853151, 2180027273, 2330708795, 2375970421, 1399407719],
            vec![0, 1, 32737, 41408833, 1282094489, 2961489665, 1529796113, 3493198193],
            vec![0, 1, 65503, 125667333, 3296703483, 2434619265, 747502215],
            vec![0, 1, 131037, 380081105, 3970173317, 1219076081],
            vec![0, 1, 262107, 1146795693, 2796259687],
            vec![0, 1, 524249, 3454279345],
            vec![0, 1, 1048535],
            vec![0, 1],
            vec![0],
        ],
        fact_data: vec![1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000],
    }));

    let t: u32 = {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        input.trim().parse().unwrap()
    };

    for _ in 0..t {
        let values: Vec<u32> = {
            let mut input: String = String::new();
            stdin.read_line(&mut input).unwrap();
            input.trim().split_whitespace().map(|x| x.parse::<u32>().unwrap()).collect()
        };

        let answer = generate_answer(values[0], values[1], values[2], &cache);
        println!("{}", answer);
    }
}

fn generate_answer(total_cards: u32, a_points: u32, b_points: u32, cache: &Rc<RefCell<Cache>>) -> u128 {
    let total_points = a_points + b_points;

    if total_points > total_cards || total_points > 0 && (a_points >= total_points || b_points >= total_points) {
        return 0;
    }

    let draws = total_cards - a_points - b_points;
    let base_points = get_base_points(a_points, b_points, &cache);
    (base_points as u128 * ncr(total_cards as u128, draws as u128, &cache) * factorial(total_cards as u128, &cache)) % MOD
}

fn get_base_points(a: u32, b: u32, cache: &Rc<RefCell<Cache>>) -> u32 {
    if b > a {
        return get_base_points(b, a, cache);
    }

    let c = (*cache).borrow();
    if c.point_data.len() > a as usize && c.point_data[a as usize].len() > b as usize {
        c.point_data[a as usize][b as usize]
    } else {
        panic!("cache doesn't have this base point value")
    }
}

fn ncr(n: u128, k: u128, cache: &Rc<RefCell<Cache>>) -> u128 {
    if k > n {
        panic!("nCr(n, k) had k > n ({} > {})", k, n)
    } else {
        factorial(n, cache) / (factorial(k, cache) * factorial(n - k, cache))
    }
}

fn factorial(n: u128, cache: &Rc<RefCell<Cache>>) -> u128 {
    if (*cache).borrow().fact_data.len() > n as usize {
        (*cache).borrow().fact_data[n as usize]
    } else {
        panic!("cache doesn't have this factorial value: {}", n)
    }
}

struct Cache {
    point_data: Vec<Vec<u32>>,
    fact_data: Vec<u128>,
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 4, 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'cache doesn't have this base point value', input/code.rs:76:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 5

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'cache doesn't have this base point value', input/code.rs:76:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 6

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'cache doesn't have this base point value', input/code.rs:76:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace