Problem B
Bump, Set, Spike, Count!
Volleyball season is starting at your local recreational center! This means all kinds of volleyball leagues are about to be in full swing: leagues for youths, seniors, amateurs, and so on. Though the Premier Adult Coed Volleyball League is considered the most prestigious league, the Youth Girl’s Volleyball League has been rising in popularity in recent years.
Again, matches in this league are played by typical volleyball rules: there are two teams consisting of six players each. Since league organizers have already solved the problem of determining if a set of touches is valid, league organizers have now set their sights on a different problem. They want to calculate the number ways to construct a valid rally consisting of exactly $N$ touches.
Because this is not a coed league, the rules governing a valid set of touches in a rally sequence are looser, as there are no restrictions around the gender of the players. A sequence of touches is only invalid if either of the following is violated:
-
A player cannot touch the ball twice in a row.
-
Since it’s a youth league, a team cannot touch the ball more than two times in a row.
The league organizers have come to you for help. The ball is in your court! Since the number of ways maybe large, output the answer module $10^9 + 7$.
Input
The input consists of a single integer $N$ $(0 \leq N \leq 5 * 10^4)$.
Output
Output the number of ways to constuct a valid sequence of touches of size $N$. Since the output may be large, output it modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 |
12 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 |
132 |
