Number of Distinct Roll Sequences
You are given an integer n.
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:
Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 10^9 + 7.
Two sequences are considered distinct if at least one element is different.
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.
Constraints
- 1 <= n <= 10^4
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.