**DIFFICULTY :**

Easy

**PREREQUISITES :**

Modular Exponentiation

**PROBLEM :**

Given M type of jewels we have to find the number of ways to place them in boxes with even number provided each box having number **i** will have **i** partitions.

**EXPLANATION :**

The number of empty slots are the summation of all even numbers upto N.

Let us assume x=floor(N/2) , then the number of empty slots are simply x*(x+1).

Each slot can be occupied by M different type of jewels thus the total number of ways are

WAYS = M^{x*(x+1)}

The above can calculated easily by using modular exponentiation while taking mod.

**TIME COMPLEXITY :**

The Time complexity is

**O(log(N))**.

**Solution :**

## Solution

```
#include"bits/stdc++.h"
using namespace std;
#define int long long
const int mod=1e9+7;
int mod_expo(int x,int y){
int ans=1,t=x;
for(int i=0;i<62;++i){
if((1LL<<i)&y) ans=(ans*t)%mod;
t=(t*t)%mod;
}
return ans;
}
void solve()
{
int n,m; cin>>n>>m;
int x=n/2;
x=x*(x+1);
m=m%mod;
cout<<mod_expo(m,x);
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int tc=1;
cin>>tc;
for(int i=1;i<=tc;++i)
{
solve();
if(i<tc)
cout<<"\n";
}
return 0;
}
```