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![],
        fact_data: vec![1],
    }));

    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 {
            return c.point_data[a as usize][b as usize];
        }
    }
    // If this part is reached, the base points could not be read from cache.

    /// Ensures that after calling this it is safe to get `point_data[a]` and that pushing to that the row has `b - 1` elements.
    /// In other words, `point_data[a].push(something)` will result in `point_data[a][b] = something`.
    /// However, if there is already data at `point_data[a][b]`, nothing will be done.
    fn ensure_prior_values(a: usize, b: usize, cache: &Rc<RefCell<Cache>>) {
        let rows = (*cache).borrow().point_data.len();
        if rows <= a {
            let mut cache = (*cache).borrow_mut();
            for _ in rows..=a {
                cache.point_data.push(vec![]);
            }
            assert_eq!(cache.point_data.len(), a + 1);
        }
        assert!((*cache).borrow().point_data.len() > a);

        let cols = (*cache).borrow().point_data[a].len();
        if cols < b {
            for i in cols..b {
                get_base_points(a as u32, i as u32, &cache); // this will also write it to cache
            }
            assert_eq!((*cache).borrow().point_data[a].len(), b);
        }

        assert!((*cache).borrow().point_data[a].len() >= b);
    }

    let hardcoded: Option<u32> =
        if b == 0 {
            if a == 0 {
                Some(1)
            } else {
                Some(0)
            }
        } else if b == 1 {
            assert!(a >= 1); // a >= b
            Some(1)
        } else {
            None
        };
    if hardcoded.is_some() {
        ensure_prior_values(a as usize, b as usize, &cache);
        (*cache).borrow_mut().point_data[a as usize].push(hardcoded.unwrap());
        return hardcoded.unwrap();
    }


    let n = a + b;
    let vertical_sum = {
        let mut sum = 0;
        let b_iter = b - 1;
        for a_iter in 1..=(a + 1) {
            sum += get_base_points(a_iter, b_iter, &cache) as u128 * ncr(n as u128, (n - a_iter - b_iter) as u128, &cache);
        }
        sum
    };

    let horizontal_sum = {
        let mut sum = 0;
        for b_iter in 1..b {
            sum += get_base_points(a, b_iter, &cache) as u128 * ncr(n as u128, (n - a - b_iter) as u128, &cache);
        }
        sum
    };

    let result = (vertical_sum - horizontal_sum) as u32;
    ensure_prior_values(a as usize, b as usize, &cache);
    assert_eq!((*cache).borrow().point_data[a as usize].len(), b as usize);
    (*cache).borrow_mut().point_data[a as usize].push(result);
    result
}

fn ncr(n: u128, k: u128, cache: &Rc<RefCell<Cache>>) -> u128 {
    if k > n {
        0
    } 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 {
        let fact = factorial(n - 1, cache) * n;
        assert_eq!((*cache).borrow().fact_data.len(), n as usize);
        (*cache).borrow_mut().fact_data.push(fact);
        fact
    }
}

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: WRONG ANSWER

Test 5

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'attempt to divide by zero', input/code.rs:134:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 6

Group: 5

Verdict: RUNTIME ERROR

thread 'main' panicked at 'attempt to divide by zero', input/code.rs:134:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace