import sequtils, strutils, math, sugar const M = 10 ^ 9 + 7 let n = stdin.readLine.parseInt var dp = @[1, 2, 2] for i in 3..