<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>

class Solution:
    def distinctSequences(self, n: int) -> int:
        '''
        * fair 6 sided dice rolled n times.. 
        * how many distinct sequences of rolls (posssibilities) can I get such that: 
            * the gcd between my previous face and the current face is 1
            * and there's a gap of over 2 between same numbered rolls.. ie., the previous two rolls should not be the same as my current.. 
        =====
        * n is at most 10**4, so recursive approach might not get accepeted.. => works!
        '''
        mod = int(1e9+7)
        @lru_cache # tricked into submission lol.. 
        def helper(previous_previous, previous, rem_n):
            if rem_n == 0: 
                return 1
            cnt = 0 
            for next_roll in range(1, 6 + 1): # inclusive of the 6th face..
                if next_roll != previous_previous and next_roll != previous: # I can take this face and remain valid only if it's not the same as my previous two roll faces.. 
                    if math.gcd(previous, next_roll) == 1: # and the gcd between my previous and current has to be one... 
                        cnt += helper(previous, next_roll, rem_n - 1) # next_roll becomes previous for the next state and previous becomes previous_previous.. 
            return cnt

        return helper(-1, -1, n) % mod
3635