2318. Number of Distinct Roll Sequences

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:

1. The greatest common divisor of any adjacent values in the sequence is equal to 1.
2. 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) > 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.

class Solution {
    int mod = 1e9 + 7;
    long long dp[10101][8][8];
    long long helper(int n, int l2, int l1) {
        if(n == 0) return 1;
        if(dp[n][l2][l1] != -1) return dp[n][l2][l1];
        long long& res = dp[n][l2][l1] = 0;
        for(int i = 1; i <= 6; i++) {
            if(__gcd(l1, i) != 1) continue;
            if(i == l2 or i == l1) continue;
            res = (res + helper(n - 1, l1, i)) % mod;
        }
        return res;
    }

public:
    int distinctSequences(int n) {
        memset(dp, -1, sizeof dp);
        return helper(n, 7, 7);
    }
};