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, 12172272321],
            vec![0, 1, 1003, 141549, 8422679, 302458313, 7789852851, 158753132437, 2722634203807],
            vec![0, 1, 2025, 453905, 39474449, 1977056433, 68767041385, 1847023092289, 40944331580049, 783282749905601],
            vec![0, 1, 4071, 1426725, 178065811, 12218582561, 564443920415, 19673873512333, 555692780332635, 13343470520917600, 281751782666559000],
            vec![0, 1, 8165, 4422913, 780889437, 72353683777, 4378051365013, 195471226248529, 6949855454616890, 207097807515365000],
            vec![0, 1, 16355, 13579309, 3352853151, 414496887689, 32472283466555, 1836770909908600, 81354047854560400],
            vec![0, 1, 32737, 41408833, 14166996377, 2313653894913, 232372145411601, 16495207645575500],
            vec![0, 1, 65503, 125667333, 59131278331, 12651113305985, 1615307882756740],
            vec![0, 1, 131037, 380081105, 244488341893, 68046385946609],
            vec![0, 1, 262107, 1146795693, 1003523639655],
            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 * 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>>) -> u128 {
    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<u128>>,
    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:77: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:77: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:77:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace