Problem Statement
A hopscotch is a well-known playground game. When preparing the game, kids will take some chalk and draw a figure consisting of some squares onto the pavement. The game is then played by hopping into those squares according to some rules that are not important here.
Here is a sample plan for the hopscotch game:
+-+-+
| |
+-+-+-+-+
| | |
+-+-+-+-+
| |
+-+-+
| |
+-+-+-+-+
| | |
+-+-+-+-+
| |
+-+-+
| |
+-+-+
When drawing a plan for the game, the kids follow several simple rules:
- The plan must consist of one or more consecutive rows of squares.
- Each row of squares must contain either one square (in the middle) or two squares next to each other.
- There can never be two consecutive rows that both contain two squares.
Zuzka wants to draw a plan that will consist of exactly N squares. Count all possible ways in which she can do so. Return that count modulo 10^9 + 7.
Definition
- Class:
- HopscotchCounting
- Method:
- count
- Parameters:
- int
- Returns:
- int
- Method signature:
- int count(int N)
- (be sure your method is public)
Constraints
- N will be between 1 and 10^6, inclusive.
Examples
2
Returns: 2
Two possible plans: either one row with two squares, or two rows with one square each.
4
Returns: 4
All four plans are shown below. Remember that two consecutive rows with two squares are not allowed. +-+-+ | | +-+-+-+-+ +-+-+ +-+-+ +-+-+ | | | | | | | | | +-+-+-+-+ +-+-+-+-+ +-+-+ +-+-+ | | | | | | | | | +-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+ | | | | | | | | | +-+-+ +-+-+ +-+-+-+-+ +-+-+
1
Returns: 1
3
Returns: 3
5
Returns: 6
70
Returns: 9736691
Don't forget to compute the answer modulo 1,000,000,007.
1000000
Returns: 544759676
998768
Returns: 485565052
907646
Returns: 285458102
876462
Returns: 515977073
784643
Returns: 663830854
689321
Returns: 206304445
536524
Returns: 369346554
400092
Returns: 888739131
321321
Returns: 834646521
14987
Returns: 196764265
88888
Returns: 648039539
999999
Returns: 134033679