Cooking dishes Problem code: COOKFOOD

Submit My Submissions All Submissions

All submissions for this problem are available.

As you might know, cooking is the process of taking a food item and subjecting it to various processes(like heating, roasting, baking etc).
A food item gets prepared after it has been subjected to exactly N processes.
The order in which the processes are applied matters(heating and then baking is different from baking and then heating). Also, the same processes cannot be aplied twice in succession. For example, heating → baking → heating is allowed, but heating → heating → baking is not allowed because 'heating' comes twice in succession.
Any given sequence A₁, A₂, A₃, ... A_N of N processes can be used to cook a food item if and only if A_i ≠ A_i+1 for all 1 ≤ i ≤ N-1.
The chefs kitchen has got K equipments for K different processes.
Chef has to cook two dishes in parallel.
This means that if the first dish is prepared by applying processes A₁, A₂, A₃, ... A_N in this order, and the second dish made by processes B₁, B₂, B₃, ... B_N, then A_i ≠ B_i for any 1 ≤ i ≤ N, because otherwise chef would need two equipments for the process A_i.
Needless to say, 1 ≤ A_i, B_i ≤ K, no two consecutive elements of A are same, and no two consecutive elements of B are same.
Given N, K your task is to find the number of ways in which in which he can prepare the two dishes. Since the number of ways can be very huge, you have to report it modulo 1000000007.

Input Description

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case is described by line containing two space separated integers, N and K as per the problem description.

Output Description

For each Test case, output a separate line containing the answer modulo 1000000007.

Sample Input

3

2 2

2 3

1 3

Sample Output

2

18

6

Explanation

For first test case, there are two ways:
a) A = {1, 2} and B = {2, 1} and b) A = {2, 1} and B = {1,2}.


For third test case, A and B are of length 1. A₀ can take three different values and for each value of A₀, B₀ can take any of the other two values.

Constraints

• T ≤ 100
• 1 ≤ N, K ≤ 10⁹

Subtask 1 (30 points):

N, K ≤ 5

Subtask 2 (20 points):

N, K ≤ 10000

the answer(without taking modulo 1000000007) will be at most 10⁴.

Subtask 3 (25 points):

N, K ≤ 10000

Subtask 4 (25 points):

No special constraints

Explanation:

Let us fill in values for the processes for A and B simultaneously from i = 1 to N. For i = 1, there are K choices for A₁ and K-1 choices for B₁. For a general other i, when we fill in A_i and B_i, we wish only that A_i != A_i-1, B_i != B_i-1 and A_i != B_i.
So, there seem to be K-1 choices for A_i != A_i-1 and similarly for B_i. but we haven't ensured that A_i != B_i. We have to still subtract from these (K-1)^2 choices, those where the two are equal to each other, but aren't equal to the previous two. There are K-2 choices for the them not being equal to the previous two, and for each of these choices, by setting A_i and B_i to this value, we get such a bad case. Thus the total number of ways of getting from i-1 to i, is (K-1)^2 - (K-2).
Another way of arriving at the above is, let us first fill in A_i and then B_i. We have two cases:
Case 1: A_i != B_i-1 and A_i-1 : there are K-2 cases.
Given this, B_i != B_i-1 as well as A_i, hence there are K-2 choices for B_i.
Case 2: A_i = B_i-1. This already gives us that A_i != A_i-1. There is 1 choice for this.
Given the above, B_i != B_i-1 only (since its anyway equal to A_i). Thus, there are K-1 choices for B_i.
The above reasoning gives us that the number of choices for A_i and B_i are (K-2)^2 + K-1. Note that this is also what we had got earlier.
Thus, final answer = (K * (K-1)) * ((K-2)^2 + K-1)^(N-1).



***** code goes here ****
#include<bits/stdc++.h>
using namespace std;
long long int mod=1000000007;
long long int pow(long long int a, long long int b)
{
     if(b==0)
     return 1;
     if(b%2==0)
    {
          return (pow(a,b/2)*pow(a,b/2))%mod;
    }
    else
    return (((pow(a,b/2)*pow(a,b/2))%mod)*a)%mod;
}
int main()

{
    int t;
    cin>>t;
    while(t--)
    {
      
    long long int n;
    cin>>n;
    long long int k;
cin>>k;
    long long int fact1=((k-2)*(k-2))%mod;
    long long int fact2=(fact1+k-1)%mod;
    long long int res=pow(fact2,n-1);
      long long int ans=(((k*(k-1))%mod)*(res))%mod;
      //cout<<"here "<<endl;
      cout<<ans<<endl;
     
}
return 0;
}
*******ends here *****