Number of Distinct Roll Sequences
You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:
- The greatest common divisor of any adjacent values in the sequence is equal to
1. - There is at least a gap of
2rolls between equal valued rolls. More formally, if the value of thei^throll is equal to the value of thej^throll, thenabs(i - j) > 2.
Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 10^9 + 7.
Two sequences are considered distinct if at least one element is different.
Example 1
Input
n = 4Output
184There are a total of 184 distinct sequences possible after excluding invalid sequences such as ones with equal values within 2 rolls or adjacent values whose greatest common divisor is not 1.
Example 2
Input
n = 2Output
22There are a total of 22 distinct sequences possible after excluding invalid adjacent pairs such as (3, 6) and (2, 4), whose greatest common divisor is not 1.
Constraints
- 1 <= n <= 10^4