Problem Statement

you are given 3 integer n , x , k where n is divisible by k you're task is to construct and array a of size n such that: the product of each segment of length k in a is equal to x the elements of a fall between 2 and x (2 a[i] x ) the array a is lexicographically minimal define p = 10^9 + 9 Find the sum of ( a[i] * p^i ) modulo 10^9 + 7 considering indexing starts from 0 if no answer exist print -1 Input Format The first line contains a integer, n , denoting the number of elements that needs to be in a . The second line contains a integer, x , denoting the condition integer. The third line contains a integer, k , denoting the length of the segment. Constraints 1 n 1 x 1 k Sample Test Cases Case 1 Input: 2 2 2 Output: -1 Explanation: -1 no way of constructing the array Case 2 Input: 2 2 1 Output: 6 Explanation: [2, 2] is the optimal array Case 3 Input: 4 10 2 Output: 60 Explanation: [2, 5, 2, 5] is the optimal array