Problem Statement

You are given q independent queries. For each query you receive three integers n , m and totalCost , and you must count a certain family of arrays. Consider an array A of length n in which every element is an integer between 1 and m (inclusive). Scan A from left to right while keeping track of the largest value seen so far. Define the cost of A as the number of positions (other than the very first one) at which a value strictly greater than every earlier value appears. In other words, start with the maximum undefined; the first element establishes the initial maximum for free, and every later element that beats the current maximum adds 1 to the cost. For a query with parameters n , m and totalCost , you must count how many distinct arrays A satisfy all of the following: A has exactly n elements. Every element A[j] satisfies 1 <= A[j] <= m (for 0 <= j < n ). The cost of A , as defined above, equals totalCost . Because this number can be very large, report it modulo 10^9 + 7