f(n)을 만드는 방법은
따라서 점화식은 f(n) = f(n - 2) * 2 + f(n - 1)이 됩니다.
var cache = Array(repeating: -1, count: 1001)
func f(_ n: Int) -> Int {
if n == 1 {
cache[n] = 1
}
if n == 2 {
cache[n] = 3
}
if cache[n] < 0 {
cache[n] = (f(n - 2) * 2 + f(n - 1)) % 10007
}
return cache[n]
}
print(f(Int(readLine()!)!))