QwazLab

use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};

trait Parser {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug;
}

impl<'a> Parser for SplitWhitespace<'a> {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug {
        self.next().expect("End of file")
            .parse::<T>().expect("Parse Error")
    }
}

//==============================================================================
use std::cmp::min;
use std::io;
use std::io::Read;

struct Input {
    num_day: i32,
    num_pie: i32,
    price: Vec<Vec<i32>>,
}

fn read_input(iter: &mut SplitWhitespace) -> Input {
    let num_day: i32 = iter.read();
    let num_pie: i32 = iter.read();
    let mut price = Vec::new();

    price.push(vec!());
    for _ in 0..num_day {
        let mut day_price = Vec::with_capacity(num_pie as usize);
        for _ in 0..num_pie {
            day_price.push(iter.read());
        }
        price.push(day_price);
    }

    Input {
        num_day: num_day,
        num_pie: num_pie,
        price: price,
    }
}

fn solve(input: Input) -> i32 {
    let num_day = input.num_day;
    let price = input.price;

    let day_size = (num_day+1) as usize;
    let mut dp = vec!(vec!(std::i32::MAX; day_size); day_size);

    dp[0][1] = 0;

    for day in 1usize..day_size {
        let mut today_price = price[day].clone();
        today_price.sort();

        let mut cost = Vec::with_capacity(day_size);
        cost.push(0);
        for (i, pie_price) in today_price.iter().enumerate() {
            let current_cost = cost[i] + pie_price + 2*(i as i32) + 1;
            cost.push(current_cost);
        }

        for stored_pie in 1usize..day_size {
            let prev_price = dp[day-1][stored_pie];
            if prev_price == std::i32::MAX { break }
            for (i, pie_cost) in cost.iter().enumerate() {
                if stored_pie-1+i >= day_size { break }
                let cell = &mut dp[day][(stored_pie-1+i) as usize];
                *cell = min(*cell, prev_price + pie_cost);
            }
        }
    }

    dp[num_day as usize][1]
}

fn main() {
    let mut buffer = String::new();
    io::stdin().read_to_string(&mut buffer).expect("Failed to read input");

    let mut iter = buffer.split_whitespace();

    let num_case: i32 = iter.read();

    for now_case in 1..(num_case+1) {
        let input = read_input(&mut iter);
        println!("Case #{}: {}", now_case, solve(input));
    }
}

use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};

trait Parser {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug;
}

impl<'a> Parser for SplitWhitespace<'a> {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug {
        self.next().expect("End of file")
            .parse::<T>().expect("Parse Error")
    }
}

//==============================================================================
use std::cmp::min;
use std::io;
use std::io::Read;

#[derive(Clone)]
struct Edge {
    from: usize,
    to: usize,
    gas: i32,
}

struct Customer {
    start: usize,
    dest: usize,
}

struct Input {
    num_city: usize,
    graph: Vec<Vec<Edge>>,
    customers: Vec<Customer>,
}

fn read_input(iter: &mut SplitWhitespace) -> Input {
    let num_city = iter.read();
    let num_edge = iter.read();
    let num_customers = iter.read();

    let city_size = (num_city+1) as usize;
    let mut graph = vec![vec!(); city_size];
    for _ in 1..city_size { graph.push(Vec::new()); }

    for _ in 0..num_edge {
        let a: usize = iter.read();
        let b: usize = iter.read();
        let gas: i32 = iter.read();

        graph[a].push(Edge {
            from: a,
            to: b,
            gas: gas,
        });
        graph[b].push(Edge {
            from: b,
            to: a,
            gas: gas,
        });
    }

    let mut customers = Vec::new();

    for _ in 0..num_customers {
        customers.push(Customer {
            start: iter.read(), dest: iter.read()
        })
    }

    Input {
        num_city: num_city,
        graph: graph,
        customers: customers,
    }
}

const INF: i32 = 7_0000_0000;

fn solve(input: Input) -> i32 {
    let customers = &input.customers;

    let city_size = (input.num_city+1) as usize;
    let customer_size = customers.len();

    let mut floyd = vec!(vec!(INF; city_size); city_size);
    for i in 1..city_size { floyd[i][i] = 0; }
    for v in input.graph {
        for edge in v {
            floyd[edge.from][edge.to] = edge.gas;
        }
    }
    for k in 1..city_size {
        for i in 1..city_size {
            for j in 1..city_size {
                if floyd[i][j] > floyd[i][k]+floyd[k][j] {
                    floyd[i][j] = floyd[i][k]+floyd[k][j];
                }
            }
        }
    }

    let mut load = vec![INF; customer_size];
    let mut preload = vec![INF; customer_size];

    let mut last_preload = 0;

    load[0] = floyd[1][input.customers[0].start];

    let last_index = input.customers.len()-1;
    for (i, customer) in input.customers.iter().enumerate() {
        if i == last_index { break }

        let next_start = input.customers[i+1].start;
        load[i+1] = min(
            load[i] + floyd[customer.start][customer.dest] + floyd[customer.dest][next_start],
            preload[i] + floyd[last_preload][customer.dest] + floyd[customer.dest][next_start],
        );

        preload[i+1] = min(
            load[i] + floyd[customer.start][next_start] + floyd[next_start][customer.dest],
            preload[i] + floyd[last_preload][next_start] + floyd[next_start][customer.dest],
        );

        if load[i+1] >= INF && preload[i+1] >= INF {
            return -1;
        }

        last_preload = customer.dest;
    }

    let customer = &customers[last_index];
    let ans = min(
        load[last_index] + floyd[customer.start][customer.dest],
        preload[last_index] + floyd[last_preload][customer.dest],
    );

    if ans == INF { -1 } else { ans }
}

fn main() {
    let mut buffer = String::new();
    io::stdin().read_to_string(&mut buffer).expect("Failed to read input");

    let mut iter = buffer.split_whitespace();

    let num_case: i32 = iter.read();

    for now_case in 1..(num_case+1) {
        let input = read_input(&mut iter);
        println!("Case #{}: {}", now_case, solve(input));
    }
}

use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};

trait Parser {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug;
}

impl<'a> Parser for SplitWhitespace<'a> {
    fn read<T, E>(&mut self) -> T
        where T: FromStr<Err = E>,
              E: Debug {
        self.next().expect("End of file")
            .parse::<T>().expect("Parse Error")
    }
}

//==============================================================================
use std::io;
use std::io::Read;

struct Input {
    num_spot: i64,
    radius: Vec<i64>,
}

fn read_input(iter: &mut SplitWhitespace) -> Input {
    let num_umbrella = iter.read();
    let num_spot = iter.read();
    let mut radius = Vec::new();

    for _ in 0..num_umbrella {
        radius.push(iter.read());
    }

    Input {
        num_spot: num_spot,
        radius: radius,
    }
}

const MOD: i64 = 1_000_000_007;

fn modinv(val: i64) -> i64 {
    let (mut a, mut b) = (val, MOD);
    let (mut x0, mut x1) = (0, 1);
    while a > 1 {
        let q = a / b;

        let t = b;
        b = a%b;
        a = t;

        let t = x0;
        x0 = x1 - q*x0;
        x1 = t;
    }
    if x1 < 0 { x1 += MOD };
    x1
}

fn solve(input: Input) -> i64 {
    let n = input.radius.len();
    let radius = &input.radius;
    if n == 1 {
        return (input.num_spot as i64) % MOD;
    }

    let radius_sum = radius.iter().fold(0, |acc, v| acc+v*2) as i64;

    let ordering = (1i64..(n-1) as i64).fold(1i64, |acc, v| acc*v%MOD);
    let inversed = (1i64..(n+1) as i64).fold(1i64, |acc, v| acc*modinv(v)%MOD);

    let mut ans = 0i64;
    for left in 0..n {
        for right in left+1..n {
            let radius_sum = radius_sum - radius[left] - radius[right];
            let free_spot = input.num_spot-1 - radius_sum;

            if free_spot < 0 {
                continue;
            }

            // n+1 H free_spot = free_spot+n C free_spot = free_spot+n C n
            let mut delta = ordering * inversed % MOD;
            for i in 0i64..n as i64 {
                delta = delta * (free_spot+n as i64 - i) % MOD;
            }
            ans = (ans + delta*2) % MOD;
        }
    }

    ans % MOD
}

fn main() {
    let mut buffer = String::new();
    io::stdin().read_to_string(&mut buffer).expect("Failed to read input");

    let mut iter = buffer.split_whitespace();

    let num_case: i32 = iter.read();

    for now_case in 1..(num_case+1) {
        let input = read_input(&mut iter);
        println!("Case #{}: {}", now_case, solve(input));
    }
}