In binary world, everything is formed by several 0s and 1s. We define bad binary strings as which contains 110 and 101. Now, we hope you can find all the good binray strings.
Given an integer N, it is clear that there will be 2^{N} different strings. Your task is to find how many binary strings are good.
Input
Only one integer N(1 <= N <= 10^{9}), which indicates the length of the strings.
Output
For each test case, output the number of good binary strings of the given length.
Ovbiously, the number will be too large, so you just output the number moded by 9973.