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

        # hints are helpful
        # sub problem is at each roll, with the last 2 rolls being whatever number
        # how many possible sequences are there
        cache = {}

        # last roll and second last row will just be set to 2 prime numbers greater than 6
        # so no dice roll will be divisible by or equal to numbers
        return self.dfs(0, n, 7, 13, cache) % (10**9 + 7)

        


    


    def dfs(self, roll_number, n, last_roll, second_last_roll, cache):

        # if we have made enough dice rolls (and they would be valid)
        if roll_number == n:
            return 1
        
        # if we have calculated this before
        if (roll_number, second_last_roll, last_roll) in cache:
            return cache[(roll_number, second_last_roll, last_roll)]
        

        # lets explore possibilities
        # keep track of total possible sequences
        total = 0

        for i in range(1, 7, 1):

            # make sure our dice roll is not equal to either of the previous 2 rolls
            # and make sure dice roll is not divisible in any way with last roll
            if i != last_roll and i != second_last_roll:
                if self.gcd_check(i, last_roll):
                    # i becomes our last roll and our last row becomes our second last roll
                    total += self.dfs(roll_number + 1, n, i, last_roll, cache)
        

        # at this roll number with our last roll being whatever
        # what are the total possible sequences
        cache[(roll_number, second_last_roll, last_roll)] = total
        return cache[(roll_number, second_last_roll, last_roll)]


    # function will check if the greatest common divisor of 2 numbers is 1
    def gcd_check(self, num_1, num_2):

        # if either of the numbers are 1
        if num_1 == 1 or num_2 == 1:
            return True
        
        # if either of the numbers are divisible by eachother (and either number is not 1)
        if num_1 % num_2 == 0 or num_2 % num_1 == 0:
            return False
        
        # if both numbers are even they can both be divised by 2
        if num_1 % 2 == 0 and num_2 % 2 == 0:
            return False
        
        return True

        
        
5085