#[allow(unused_imports)] use std::cmp::{max, min}; #[allow(unused_imports)] use std::collections::{HashMap, HashSet}; mod util { use std::io::stdin; use std::str::FromStr; use std::fmt::Debug; #[allow(dead_code)] pub fn line() -> String { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().to_string() } #[allow(dead_code)] pub fn get() -> T where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().parse().unwrap() } #[allow(dead_code)] pub fn gets() -> Vec where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn get2() -> (T, U) where ::Err: Debug, ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) } } #[allow(unused_macros)] macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } } const M: usize = 1000000007; fn main() { let n: usize = util::get(); let mut dp = vec![vec![0; 3]; max(n + 1, 4)]; dp[1][0] = 1; dp[2][1] = 1; dp[3][2] = 1; for i in 1..n + 1 { if i >= 1 { dp[i][0] = (dp[i][0] + dp[i - 1][1]) % M; dp[i][0] = (dp[i][0] + dp[i - 1][2]) % M; } if i >= 2 { dp[i][1] = (dp[i][1] + dp[i - 2][0]) % M; dp[i][1] = (dp[i][1] + dp[i - 2][2]) % M; } if i >= 3 { dp[i][2] = (dp[i][2] + dp[i - 3][0]) % M; dp[i][2] = (dp[i][2] + dp[i - 3][1]) % M; } } println!("{}", dp[n].iter().fold(0, |a, &b| (a + b) % M)); }