MOD = 1000000007 n = gets.to_i if n == 1 p 1 elsif n < 4 p 2 else a = Array.new(n) a[0..2] = [1,2,2] 3.upto(n - 1){|i| a[i] = (a[i - 3] + a[i - 2]) % MOD } p a[n - 1] end