Signal timetable count
HardOnline Assessment
Count the legal timetables of a single railway track for one day, and the freight trains they contain.
A single-track section is watched minute by minute. A timetable for a day of minutes minutes assigns every minute either to idle (.) or to a train; a train always occupies consecutive minutes, and every minute of the day belongs to exactly one thing. There are three kinds of train:
- a local (
LL) occupies 2 minutes and has no restrictions; - an express (
XXX) occupies 3 minutes and must be followed by at least one idle minute, unless it finishes at the last minute of the day; - a freight (
FFF) occupies 3 minutes and must be preceded by at least two idle minutes. The start of the day counts as idle time, so a freight may start in the first minute (nothing before it) or in the second minute (after one idle minute).
Two timetables are different if some minute differs. Trains may follow each other directly whenever the rules above allow it, and a train may not be cut off by the end of the day.
For example, with 3 minutes there are 5 timetables: ..., LL., .LL, XXX and FFF.
Input: minutes, an integer.
Output: a list [timetables, freight_trains]: the number of legal timetables, and the total number of freight trains over all of those timetables (a timetable with two freights contributes 2), each taken modulo 1000000007.
Example 1
- Input:
- [3]
- Output:
- [5,1]
- Explanation
- The five timetables of a 3-minute day are
...,LL.,.LL,XXX(the express ends exactly at the end of the day, so it needs no idle minute after it) andFFF(the start of the day counts as idle time). Only the last one contains a freight, so the answer is[5, 1].
Example 2
- Input:
- [5]
- Output:
- [16,4]
- Explanation
- Of the 16 timetables of a 5-minute day, exactly 4 contain a freight:
FFF..,FFFLL,.FFF.and..FFF. A freight needs two idle minutes right before it (the start of the day counts), soLLFFFis illegal. Two freights never fit in 5 minutes, so the totals are[16, 4].
Example 3
- Input:
- [7]
- Output:
- [53,16]
- Explanation
- A 7-minute day has 53 timetables and 16 freight trains in total. An express has to be followed by an idle minute, and that single minute is not enough to precede a freight, so
XXX.FFFis illegal; so areFFF.FFFand.LL.FFF. A freight needs two idle minutes right before it, or the start of the day.
Constraints
1 <= minutes <= 10^18- the answer is taken modulo
1000000007