Boy Yaroslav wanted to eat $$$n$$$ whoppers for lunch. First he eats the first whopper, then the second, the third, and so on. The tastiness of the $$$i$$$-th whopper is $$$a_i$$$.

Since Yaroslav has ADHD, it is hard for him to eat a whopper when its tastiness is different from the tastiness of the previous whopper he ate, so he can do this exactly $$$m$$$ times. He became interested in how many different sequences of whoppers he can eat if the tastiness of each whopper can be any integer from $$$1$$$ to $$$k$$$.

More formally, you need to count the number of sequences $$$a$$$ of length $$$n$$$, consisting of numbers from $$$1$$$ to $$$k$$$, such that there are exactly $$$m$$$ indices $$$i$$$ ($$$2 \le i \le n$$$) for which $$$a_i \ne a_{i-1}$$$.

Since the number of such sequences can be very large, print the answer modulo $$$10^9 + 7$$$.

The tests for this problem consist of four groups. Points for each group are given only if all tests of this group and all tests of some previous groups are passed. Please note that passing the sample tests is not required for some groups. The final score for each group is equal to the maximum score obtained for this group over all submissions.

Working in the kitchen of "Burger King" is real art, especially when it comes to making the legendary Whopper!

In front of you there is a rectangular organizer with ingredients, represented as a matrix of size $$$n \times m$$$. The organizer is filled with so many different components (from a crunchy pickled cucumber to the signature sauce) that each of them is unique. Each cell has an importance level from $$$0$$$ to $$$n \cdot m - 1$$$, and every level appears exactly once. The importance level of the ingredient located in row $$$i$$$ and column $$$j$$$ is $$$a_{i, j}$$$.

To make a burger, you must use one careful move with a special rectangular spatula and take some rectangular submatrix from the organizer. However, the spatula has limited size, so the area of the chosen submatrix, that is, the number of cells in it, must not exceed $$$k$$$.

The taste of the perfect Whopper is determined by how consistently the basic ingredients are collected. Formally, the taste of the burger is equal to the $$$\operatorname{MEX}$$$ of the set of importance levels of the ingredients in the chosen submatrix.

Recall that $$$\operatorname{MEX}$$$ (Minimum Excluded) of a set of numbers is the smallest non-negative integer that does not belong to this set. For example, $$$\operatorname{MEX}$$$ of the set $$$\{0, 1, 3, 4\}$$$ is $$$2$$$, and $$$\operatorname{MEX}$$$ of the set $$$\{1, 2\}$$$ is $$$0$$$.

While the restaurant manager turned away to the cash desk, you have a chance to use your sleight of hand and swap the contents of any two different cells of the organizer at most once. You may also choose not to change anything at all.

Determine the maximum possible taste of the Whopper that you can get if you optimally make at most one swap and then choose a rectangular submatrix of ingredients.

The tests for this problem consist of five groups. Points for each group are given only if all tests of this group and all tests of some previous groups are passed. Please note that passing the sample tests is not required for some groups. The final score for each group is equal to the maximum score obtained for this group over all submissions.

What can be better than a whopper? Only a double whopper! And what about a $$$k$$$-whopper? Bob wants to eat like a pig, but Alice wants to stop him!

A reform was made in "Burger King", and now there are $$$n$$$ cash desks there, numbered from $$$0$$$ to $$$n - 1$$$. For each cash desk, two numbers are given: $$$a_i$$$ and $$$k_i$$$ — the change in the number of patties in the whopper after visiting this cash desk, and its importance, respectively. The value $$$a_i$$$ can be negative, then the number of patties decreases.

All visitors start at cash desk $$$n - 1$$$ and then move between cash desks until they reach cash desk $$$0$$$. While at cash desk with number $$$i$$$ ($$$0 \lt i \lt n$$$), one can move either to cash desk $$$i - 1$$$, or choose a number $$$b$$$ ($$$1 \lt b \le k_i$$$) and move to cash desk $$$\lfloor i / b \rfloor$$$.

Before visiting cash desk $$$n-1$$$, Bob's whopper contains $$$10^{100}$$$ patties (did you think we were bluffing in the first paragraph?). When visiting cash desk with number $$$i$$$, exactly $$$a_i$$$ patties are added to the whopper, and it is impossible not to take them. Alice and Bob make moves alternately, and Alice moves first. Alice wants to minimize the final number of patties, while Bob wants to maximize it. On their move, Alice or Bob chooses the next cash desk to move to.

Determine how many patties will be in the whopper if both players play optimally.

The tests for this problem consist of seven groups. Points for each group are given only if all tests of this group and all tests of some previous groups are passed. Please note that passing the sample tests is not required for some groups. The final score for each group is equal to the maximum score obtained for this group over all submissions.

In the times of the Great Angus, when ancient recipes in the kingdom of "Burger King" were only starting to appear, each element of the array was treated as a separate ingredient for the sacred burger. The number $$$a_i$$$ meant which ingredient was on the $$$i$$$-th shelf of the royal storage, and there were $$$n$$$ shelves in total.

But on the day of the Great Angus Celebration, the priests were given an unusual task. From the segment of the storage from the $$$l$$$-th to the $$$r$$$-th shelf, they had to collect exactly $$$k$$$ baskets of ingredients, such that:

• the ingredient from the $$$i$$$-th shelf must be in at most one basket;
• in each basket, the $$$\operatorname{MEX}$$$ of the set of ingredients must be equal to $$$x$$$.

Here, $$$\operatorname{MEX}$$$ — is the smallest non-negative integer that is not in the chosen basket: it was considered the number of the missing ingredient in the great Angus recipe.

The priests of "Burger King" believed that if they count the number of ways to collect the baskets like this on a segment of the storage, then on that day the Angus will be especially juicy, and the kingdom will be full and happy.

That is exactly what the wise men do: for each query with segment borders $$$[l, r]$$$ and number $$$x$$$, they count how many ways there are to choose a set of $$$k$$$ pairwise non-intersecting subsequences $$$a_l, a_{l+1}, \ldots, a_r$$$ such that each subsequence has $$$\operatorname{MEX}$$$ equal to $$$x$$$.

Note that two subsequences are considered different if they consist of elements with different indices in the array $$$a$$$. For example, in the array $$$a = [0, 0, 0]$$$ on the segment $$$[1,3]$$$ there are $$$7$$$ non-empty subsequences with $$$\operatorname{MEX}$$$ equal to $$$1$$$.

You have to act as a wise man and count the number of such ways. Since this number can be very large, it is enough to print the answers modulo $$$10^9 + 7$$$.

The tests for this problem consist of eight groups. Points for each group are given only if all tests of this group and all tests of some previous groups are passed. Please note that passing the sample tests is not required for some groups. The final score for each group is equal to the maximum score obtained for this group over all submissions.