Hello, Codeforces community!

I recently faced an interesting problem during a company online assessment, and I wanted to share it with you all. Unfortunately, I couldn't solve it, and I’m reaching out for your help.

Problem Description

You are given three integers: A,B,C. Your task is to count the number of possible arrays of size A that satisfy the following conditions: - The elements in the array are chosen from the set {1, 2, ..., C}. - The maximum size of any subarray containing identical elements is at most B.

Input

An integer A: the size of the array. (1<=A<=10^9) An integer B: the maximum size of a subarray containing identical elements. (1<=B<=min(50,A)) An integer C: the maximum value for any element in the array (elements are chosen from {1, 2, ..., C}). (1<=C<=10^5)

Output An integer representing the number of valid arrays.(Return the value modulo 1e9+7)

Example For A=3 , B=1 , C=3 the answer is 12 and the valid subarrays are [1, 2, 1], [1, 2, 3], [1, 3, 1], [1, 3, 2], [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2], [3, 1, 2], [3, 1, 3], [3, 2, 1], [3, 2, 3]

I am thinking of dp but how to handle such large A ? Is there any problem it could be reduced to ?