main :: IO () main = print . solve =<< readLn solve :: Int -> Int solve n = solve' 1 n (1, 0, 0) where reduce :: Int -> Int reduce a = a `mod` (1000000007) solve' :: Int -> Int -> (Int, Int, Int) -> Int solve' i x (a, aa, ab) | i == x = reduce (a + aa + ab) | otherwise = solve' (i + 1) x (ab, a, reduce (a + aa))