1014 - Binary String
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 2N different strings. Your task is to find how many binary strings are good.
- Input
- Only one integer N(1 <= N <= 109), 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