You roll an ordinary six-sided die (faces 1–6) any number of times and add up the results. How many different ordered sequences of rolls add up to exactly n? [1, 2] and [2, 1] count as different sequences.
Implement dice_combinations(n: int) -> int, returning the count modulo 10^9 + 7.
dice_combinations(2) # 2 [1,1] [2]
dice_combinations(3) # 4 [1,1,1] [1,2] [2,1] [3]
dice_combinations(7) # 63
Constraints: 1 <= n <= 10^6.
Aim for O(n), and avoid recursion: a million levels deep overflows Python's stack.
Show hint
Think about the last roll. It is one of six faces, and each choice leaves a smaller target to count.