A board game token moves forward along a track. Each turn it jumps by one of the lengths in parts (any length, any number of times). Count the different sequences of jumps that land it exactly target squares ahead. Order matters: 1, 2 and 2, 1 are two different sequences.
Write count_ordered_ways(parts: list[int], target: int) -> int. The count can be huge, so return it modulo 1_000_000_007.
count_ordered_ways([1, 2, 3], 4) # 7 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1
count_ordered_ways([2, 3], 7) # 3 2+2+3, 2+3+2, 3+2+2
count_ordered_ways([5], 3) # 0
count_ordered_ways([4, 1], 4) # 2 4, 1+1+1+1
Constraints: 1 <= len(parts) <= 100, the lengths are distinct and in [1, 10^4], 1 <= target <= 10^4.
Listing every sequence is exponential (there are more than 10^2000 of them for [1, 2] and 10^4). Aim for O(target × len(parts)).
Show hint
every sequence that reaches t ends with some last jump p, and what comes before it is a sequence reaching t - p. Fill in the counts for 0, 1, ..., target in order.