Leetcode 2318. Number of Distinct Roll Sequences

Count the number of length-n sequences of die faces (1..6) where every adjacent pair has gcd=1 and equal values are at least 3 positions apart, returning the result modulo 10^9+7. This is solved by DP on the last two rolls (36 states) or equivalently by exponentiating a 36×36 transition matrix to handle n up to 10^4 efficiently.