<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, sides=6) -> int:
        # roll an m sided dice n times 
        # number of unique sequences of rolls possible such that 
        # gcd of adjacent values == 1
        # at least gap of 2 rolls between equal values 
        if n == 1 : 
            return sides # (any digit solo)
        elif n == 2 : 
            count = 0 
            for i in range(1, sides+1) : 
                for j in range(1, sides+1) : 
                    if i == j : 
                        continue 
                    elif math.gcd(i, j) != 1 : 
                        continue 
                    else : 
                        count += 1 
            return count 
        else : 
            # to count the combinations 
            total_combinations = 0 
            # mod as needed 
            mod = 1_000_000_007 
            # make a mapping of the set of values that each can take with the next item 
            mapping = dict()
            for i in range(1, sides+1) : 
                set_for_i = set() 
                for j in range(1, sides+1) : 
                    if i == j : 
                        continue 
                    elif math.gcd(i, j) != 1 : 
                        continue 
                    else : 
                        set_for_i.add(j) 
                mapping[i] = set_for_i 

            # build a tuple map of the options that are linked each pairing 
            tuple_maps = collections.defaultdict(dict) 
            pair_mappings = dict() 
            # by looping for i in range 1 - 6 inclusive 
            for i in range(1, sides+1) : 
                # twice over 
                for j in range(1, sides+1) : 
                    # skipping on matches and j not in mapping[i] 
                    if i == j : 
                        continue 
                    elif j not in mapping[i] : 
                        continue 
                    else : 
                        # and get the difference of the mapping current with i and j then map appropriately 
                        current_options = mapping.get(j, {})
                        options = tuple(current_options.difference(set([i, j]))) if current_options else {} 
                        tuple_maps[i][j] = options 
                        pair_mappings[(i, j)] = 1 
                
            # loop n_i in range 2 to n (already made 2 roles to build the above )
            for n_i in range(2, n) : 
                # set up a current mapping to replace pair mappings 
                current_mapping = collections.defaultdict(int)
                # loop and update over pair mappings items 
                for (a, b), freq in pair_mappings.items() : 
                    # by updating over partners as appropriate 
                    for partner in tuple_maps[a][b] : 
                        # the components as needed 
                        current_mapping[(b, partner)] = (current_mapping[(b, partner)] + freq) % mod 
                # and then resetting the current 
                pair_mappings = current_mapping 
                
            # when done loop over values, summing each and modulo as needed 
            for freq in pair_mappings.values() : 
                total_combinations = (total_combinations + freq) % mod 
                
            # return when done 
            return total_combinations
484