Hotel Room Assignment
Time limit1sMemory limit1024 MB
Count the ways to place any number of guests on N floors of two rooms each so that no two guests share a floor or sit vertically adjacent, modulo 1e9+7.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics, Matrix, Math
- Solved
- No attempts yet
Problem
Seongmin runs an N-story hotel with 2 rooms on each floor. (Ignore how this is physically possible.)
Each room has a positive integer number. The quotient of the number divided by 100 gives the floor, and the remainder is either 1 or 2. The two rooms on a floor have different remainders. Two rooms with the same remainder and quotients differing by 1 are vertically adjacent. For example, floor 1 has rooms 101 and 102, and floor 2 has rooms 201 and 202.
One day the government declares "social distancing" because the epidemic has worsened, so Seongmin must be more careful when guiding customers who want to stay at the hotel.
When assigning rooms, the following conditions must be met.
- To keep social distance, customers cannot be placed on the same floor at the same time. For example, customers cannot be placed in rooms 101 and 102 at the same time.
- Because the epidemic can spread through the air, customers cannot be placed vertically adjacent to each other. For example, customers cannot be placed in rooms 101 and 201 at the same time.
How many ways can Seongmin, running an N-story hotel, place customers?
Input
The integer N, the number of floors of the hotel Seongmin runs, is given as input. (1 ≤ N ≤ 10^18)
Output
Output the number of ways Seongmin can place customers in rooms, modulo 10^9 + 7.