Count Valid Arrays

Problem Statement

Count Valid Arrays Problem Description An array is called valid if it contains no subarray longer than B in which all elements are identical. Every element of the array must be an integer from the range [1, C] . Count how many valid arrays of length A exist. Since the count can be very large, print it modulo 10 9  + 7 . A subarray is a block of consecutive positions. "Longer than B " means length B + 1 or more, so a block of exactly B equal values is still allowed — Example 2 relies on this. Input Format A single line containing three space-separated integers A , B and C . (inferred — the source presents A, B and C as function arguments and does not describe a stdin layout. They are read from standard input in the order A, B, C, which is the order the question's existing starter code already uses.) Output Format Print a single integer: the number of valid arrays of length A , taken modulo 10 9  + 7 . (inferred — the source says "return an