Die Rolls Without Close Repeats

Hard

A standard six-sided die is rolled rolls times and the results are written down in order. A sequence is allowed if: - every two adjacent values are coprime (their greatest common divisor is 1); - equal values are more than two positions apart: if positions i and j show the same value, then |i − j| > 2. Count the distinct allowed sequences. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

rolls=1 → 6

With a single roll, any of the six faces works.

Example 2

rolls=2 → 22

Ordered pairs of distinct coprime faces work, such as (1, 6), (5, 4), (3, 2). Pairs like (2, 4), (3, 6) and pairs of equal faces do not. 22 pairs in total.

Example 3

rolls=3 → 66

For example, (1, 2, 3) works but (1, 2, 1) does not: equal values are only one roll apart.

Constraints

1 ≤ rolls ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Memoization Dynamic Programming

Similar problems

Every Way to Space the Words Hard Longest Uphill Walk Hard Clear the Marble Row Hard Clearing Colored Cubes Hard Six-Cell Tile Slider Hard

Input

rolls=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 23 tests on the server, hidden ones included.