use std::io::stdin; fn main(){ let n: usize = getvec()[0]; println!("{}", solve(n)); } fn solve(n: usize) -> usize { let mut dp: Vec> = Vec::new(); dp.push(vec![1, 1, 1]); dp.push(vec![1, 0, 0]); dp.push(vec![0, 1, 0]); dp.push(vec![0, 0, 1]); for i in 1..n { dp[i+1][0] = (dp[i+1][0]+dp[i][1]+dp[i][2]) % 1000000007; dp[i+2][1] = (dp[i+2][1]+dp[i][0]+dp[i][2]) % 1000000007; let x = (dp[i][0]+dp[i][1]) % 1000000007; dp.push(vec![0, 0, x]); } dp[n].iter().fold(0, |acc, x| acc+x) % 1000000007 } #[allow(dead_code)] fn getline() -> String { let mut s = String::new(); match stdin().read_line(&mut s){ Ok(_) => {s.trim().to_string()} Err(_) => String::new() } } #[allow(dead_code)] fn getvec() -> Vec{ let line = getline(); line.split_whitespace().filter_map(|x| x.parse().ok()).collect() } #[allow(dead_code)] fn getpair() -> (usize, usize){ let nm = getvec(); (nm[0], nm[1]) }