소스 코드 제출

# import sys
# # limit_number = 15000
# # sys.setrecursionlimit(limit_number)
# #
# # memo = [0] * 1000000
# #
# # def block(n):
# #     if n == 1 or n == 2:
# #         return n
# #
# #     if memo[n] != 0:
# #         return memo[n]
# #
# #     memo[n] = block(n-1)%100000007 + block(n-2)%100000007
# #     return memo[n]%100000007
# #
# # k = int(input())
# # print(block(k)%100000007)
# 
# # import sys
# # limit_number = 15000
# # sys.setrecursionlimit(limit_number)
# # a = [0] * 100000
# #
# # def block(n) :
# #     if n==3 :
# #         return 2
# #
# #     if a[n]!=0 :
# #         return a[n]
# #
# #     if n%3!=0 :
# #         a[n] = 0
# #     else :
# #         a[n]= block(n-3) * 2
# #     return a[n]
# #
# # n = int(input())
# # print(block(n)%100000007)
# 
# import sys
# limit_number = 15000
# sys.setrecursionlimit(limit_number)
# a = [0] * 100000
# 
# def block(n) :
#     if n==1 or n==2 :
#         return n
# 
#     if a[n]!=0 :
#         return a[n]
# 
#     if n==3 :
#         a[n] = 5
#     else :
#         a[n] = block(n-1) + 4
#     return a[n]
# 
# n = int(input())
# print(block(n)%100007)