Kortit II

use std::cell::RefCell;
use std::io;
use std::rc::Rc;
 
const MOD: u64 = 10u64.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>>) -> u32 {
    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, draws, &cache)) % MOD) as u32
}
 
fn get_base_points(a: u32, b: u32, cache: &Rc<RefCell<Cache>>) -> u64 {
    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<u64> =
        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) * ncr(n, n - a_iter - b_iter, &cache);
        }
        sum
    };
 
    let horizontal_sum = {
        let mut sum = 0;
        for b_iter in 1..b {
            sum += get_base_points(a, b_iter, &cache) * ncr(n, n - a - b_iter, &cache);
        }
        sum
    };
 
    let result = (vertical_sum - horizontal_sum) % MOD;
    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: u32, k: u32, cache: &Rc<RefCell<Cache>>) -> u64 {
    if k > n {
        0
    } else {
        (factorial(n, cache) / ((factorial(k, cache) * factorial(n - k, cache)) % MOD)) % MOD
    }
}
 
fn factorial(n: u32, cache: &Rc<RefCell<Cache>>) -> u64 {
    if (*cache).borrow().fact_data.len() > n as usize {
        (*cache).borrow().fact_data[n as usize]
    } else {
        let fact = (factorial(n - 1, cache) * n as u64) % MOD;
        assert_eq!((*cache).borrow().fact_data.len(), n as usize);
        (*cache).borrow_mut().fact_data.push(fact);
        fact
    }
}
 
struct Cache {
    point_data: Vec<Vec<u64>>,
    fact_data: Vec<u64>,
}

Test 1

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 5

Verdict: TIME LIMIT EXCEEDED