use std::collections::HashMap;
fn main() {
    let mut arr: Vec<Vec<isize>> = vec![vec![1, 2, 3], vec![3], vec![2, 4]];
    let ans = coop_develop(&mut arr);
    println!("ans = {}", ans);
}

fn coop_develop(skills: &mut Vec<Vec<isize>>) -> isize {
    const MOD: isize = 1000000007;
    let n = skills.len() as isize;
    // key : 子集
    // value : 个数
    let mut no_full_sets_nums: HashMap<isize, isize> = HashMap::new();
    for people in skills.iter_mut() {
        fill_no_full_map(people, 0, 0, true, &mut no_full_sets_nums);
    }
    let mut cnts_nums: HashMap<isize, isize> = HashMap::new();
    let mut minus: isize = 0;
    for people in skills.iter_mut() {
        let mut status: isize = 0;
        for skill in people {
            status = (status << 10) | *skill;
        }
        minus += if no_full_sets_nums.contains_key(&status) {
            *no_full_sets_nums.get(&status).unwrap()
        } else {
            0
        };
        minus += if cnts_nums.contains_key(&status) {
            *cnts_nums.get(&status).unwrap()
        } else {
            0
        };
        cnts_nums.insert(
            status,
            if cnts_nums.contains_key(&status) {
                *cnts_nums.get(&status).unwrap()
            } else {
                0
            } + 1,
        );
    }
    let ans = n * (n - 1) / 2;
    return (ans - minus) % MOD;
}

fn fill_no_full_map(
    people: &mut Vec<isize>,
    i: isize,
    status: isize,
    full: bool,
    no_full_sets_nums: &mut HashMap<isize, isize>,
) {
    if i == people.len() as isize {
        if !full {
            no_full_sets_nums.insert(
                status,
                if no_full_sets_nums.contains_key(&status) {
                    *no_full_sets_nums.get(&status).unwrap()
                } else {
                    0
                } + 1,
            );
        }
    } else {
        fill_no_full_map(people, i + 1, status, false, no_full_sets_nums);
        fill_no_full_map(
            people,
            i + 1,
            (status << 10) | people[i as usize],
            full,
            no_full_sets_nums,
        );
    }
}