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


	The greatest common divisor of any adjacent values in the sequence is equal to 1.
	There is at least a gap of 2 rolls between equal valued rolls. More formally, if the value of the ith roll is equal to the value of the jth roll, then abs(i - j) &gt; 2.


Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 109 + 7.

Two sequences are considered distinct if at least one element is different.

&nbsp;
Example 1:

Input: n = 4
Output: 184
Explanation: 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.

Example 2:

Input: n = 2
Output: 22
Explanation: 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.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 104


mod=1000000007
@cache
def func(n,prev,pp):
    if n==0:
        return 1
    ans=0
    for i in range(1,7):
        if prev==-1:
            ans+=func(n-1,i,prev)
            ans=ans%mod
        elif pp==-1:
            if(math.gcd(i,prev)==1 and i!=prev):
                ans+=func(n-1,i,prev)
                ans=ans%mod
        else:
            if(math.gcd(i,prev)==1 and i!=prev and i!=pp):
                ans+=func(n-1,i,prev)
                ans=ans%mod
    return ans;
class Solution:
    
            
    def distinctSequences(self, n: int) -> int:
        return func(n,-1,-1)
class Solution {
    static long[][] dp;
    public int distinctSequences(int n) {
        if(n==1) return 6;
        int mod = 1_000_000_007;
        dp =new long[][]
                {
                    {0,1,1,1,1,1},
                    {1,0,1,0,1,0},
                    {1,1,0,1,1,0},
                    {1,0,1,0,1,0},
                    {1,1,1,1,0,1},
                    {1,0,0,0,1,0}
                };
        for(int i=2;i<n;i++){
            long[][] temp = new long[6][6];
            for(int j=0;j<6;j++){
                for(int k=0;k<6;k++){
                    long total = 0;
                    if(dp[j][k] == 0) continue;
                    for(int l=0;l<6;l++){
                        total = (total + ((l==k)?0:dp[l][j]))%mod;
                    }
                    temp[j][k] = total;
                }
            }
            dp = temp;
        }
        long result = 0;
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                result = (result + dp[i][j])%mod;
            }
        }
        return (int)(result);
    }
}
class Solution {
private:
	int mod = 1e9+7;

	int f(int ind,int prev1,int prev2,int n){
		//Base Case
		if(ind == n) return 1;

		int ans = 0;
		for(int i = 1;i <= 6;i++) //Exploring all possible values
			if(prev1 != i && prev2 != i && (prev1 == 0 || __gcd(prev1,i) == 1))
				ans = (ans + f(ind+1,i,prev1,n))%mod;

		return ans;
	}
public:
	int distinctSequences(int n) {
		return f(0,0,0,n);
	}
};
var distinctSequences = function(n) {
    // 3D DP [n + 1][7][7] => rollIdx, prev, prevPrev
    const dp = Array.from({ length: n + 1}, () => {
        return new Array(7).fill(0).map(() => new Array(7).fill(0));
    });

    const gcd = (a, b) => {
        if(a < b) [b, a] = [a, b];
        while(b) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    const ds = (n, p = 0, pp = 0) => {
        if(n == 0) return 1;
        if(dp[n][p][pp] == 0) {
            for(let i = 1; i <= 6; i++) {
                if((i != p && i != pp) && (p == 0 || gcd(p, i) == 1)) {
                    dp[n][p][pp] = (dp[n][p][pp] + ds(n - 1, i, p)) % 1000000007;
                }
            }
        }
        return dp[n][p][pp];
    }
    return ds(n);
};
Number of Distinct Roll Sequences