<p>You are given an integer <code>n</code>. You roll a fair 6-sided dice <code>n</code> times. Determine the total number of <strong>distinct</strong> sequences of rolls possible such that the following conditions are satisfied:</p>

<ol>
	<li>The <strong>greatest common divisor</strong> of any <strong>adjacent</strong> values in the sequence is equal to <code>1</code>.</li>
	<li>There is <strong>at least</strong> a gap of <code>2</code> rolls between <strong>equal</strong> valued rolls. More formally, if the value of the <code>i<sup>th</sup></code> roll is <strong>equal</strong> to the value of the <code>j<sup>th</sup></code> roll, then <code>abs(i - j) &gt; 2</code>.</li>
</ol>

<p>Return <em>the<strong> total number</strong> of distinct sequences possible</em>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>Two sequences are considered distinct if at least one element is different.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> 184
<strong>Explanation:</strong> Some of the possible sequences are (1, 2, 3, 4), (6, 1, 2, 3), (1, 2, 3, 1), etc.
Some invalid sequences are (1, 2, 1, 3), (1, 2, 3, 6).
(1, 2, 1, 3) is invalid since the first and third roll have an equal value and abs(1 - 3) = 2 (i and j are 1-indexed).
(1, 2, 3, 6) is invalid since the greatest common divisor of 3 and 6 = 3.
There are a total of 184 distinct sequences possible, so we return 184.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 22
<strong>Explanation:</strong> Some of the possible sequences are (1, 2), (2, 1), (3, 2).
Some invalid sequences are (3, 6), (2, 4) since the greatest common divisor is not equal to 1.
There are a total of 22 distinct sequences possible, so we return 22.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
</ul>

from functools import lru_cache
from math import gcd

class Solution:
    def distinctSequences(self, n: int) -> int:
        
        @lru_cache(None)
        def fn(n, p0, p1): 
            """Return total number of distinct sequences."""
            if n == 0:
                return 1
            
            ans = 0
            for x in range(1, 7): 
                # Check if x can be placed in the current position
                # x should not be equal to the previous two rolls (p0, p1)
                # gcd(x, p0) should be 1 to ensure adjacent rolls are coprime
                if x not in (p0, p1) and gcd(x, p0) == 1:
                    ans += fn(n-1, x, p0)
            
            return ans % 1_000_000_007
        
        # Start the recursion with n rolls left, and no previous rolls (-1, -1)
        return fn(n, -1, -1)

# Explanation of the solution approach:

# 1. We use a recursive function `fn` with memoization (using `lru_cache`) to calculate the number of distinct sequences.
# 2. The function `fn(n, p0, p1)` returns the number of valid sequences of length `n` where `p0` is the last roll and `p1` is the second last roll.
# 3. If `n` is 0, it means we have successfully created a valid sequence, so we return 1.
# 4. We iterate over all possible dice rolls (1 to 6) and check if the current roll `x` can be placed:
#    - `x` should not be equal to the last two rolls (`p0` and `p1`) to satisfy the condition of a gap of at least 2 rolls between equal values.
#    - The greatest common divisor of `x` and `p0` should be 1 to ensure adjacent rolls are coprime.
# 5. If `x` is valid, we recursively call `fn` with one less roll (`n-1`) and update the last two rolls to `x` and `p0`.
# 6. The result is accumulated in `ans` and returned modulo `1_000_000_007` to handle large numbers.
# 7. The initial call to `fn` is made with `n` rolls and no previous rolls (`-1, -1`), which starts the recursive process.
525500