/// Имеется прямоугольное поле размера `n \times m`. Нужно посчитать число способов замостить его
/// доминошками размера `1 \times 2`. Доминошки могут быть повернуты горизонтально или вертикально,
/// но они не должны перекрываться или выходить за пределы поля. Поскольку ответ может быть
/// достаточно большим, требуется вывести его по модулю `k` (остаток от деления ответа на `k`).
pub fn solve() {
    let m: u32 = 16;
    let n: u32 = 16;
    let bound: u64 = 1_000_000_000;
    let mut d = vec![0u64; 2_u32.pow(m) as usize];
    d[0] = 1;
    // optimized to the left shifts
    let pow2_m2 = 2_u32.pow(m - 2);
    let pow2_m1 = 2_u32.pow(m - 1);
    for _ in 0..n {
        for i in 0..m - 1 {
            for k in 0..pow2_m2 {
                let k0 = insert_00(i, k);
                let t = 1 << i;
                let k1 = k0 + t;
                let k2 = k1 + t;
                let k3 = k2 + t;
                d.swap(k0, k1);
                d.swap(k2, k3);
                d[k2] += d[k1];
                d[k2] %= bound;
            }
        }
        for k in 0..pow2_m1 {
            let k0 = k as usize;
            let k1 = k0 + pow2_m1 as usize;
            d.swap(k0, k1);
        }
    }
    println!("m = {}, n = {}, d = {}", m, n, d[0]);
}

/// функция вставляет два нулевых бита в позицию i,
/// пример для k == 63 и i == 0, 1, ... , 6
///   11111100
///   11111001
///   11110011
///   11100111
///   11001111
///   10011111
///   00111111
fn insert_00(i: u32, k: u32) -> usize {
    let mut x = k.clone();
    let mut y = k.clone();
    x <<= 2;
    x &= (3_u32 << i).not();
    x &= 0_u32.not() << i;
    y &= (0_u32.not() << i).not();
    x |= y;
    x as usize
}