Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 146
Solved: 30
 Description
 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.
 sample input

3
 sample output

6
 hint
 source
 ACman
Submit