Problem G
Odd A's, Even B's
Fredrik prefers to have his life in perfect order. His i’s should be dotted, his t’s should be crossed, his a’s should be odd and his b’s should be even.
Odd a’s? Even b’s? You see, Fredrik is a great fan of the Swedish pop wonder ABBA. As a tribute, he likes writing songs containing only the notes a and b. Furthermore, the sequence of notes in the song may not have an even-length contiguous sequence of a’s, or an odd-length contiguous sequence of b’s. If such sequences were good enough for ABBA, they are good enough for Fredrik!
Can you compute the number of songs Fredrik could possibly write if they are to contain exactly $n$ notes?
Input
The first and only line of input contains the integers $n$ ($1 \le n \le 100$), the number of notes in Fredrik’s song.
Output
Output the number of songs Fredrik can write. Since this number can be very large, output it modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 |
2 |
