MATBREAK - CodeChef Easy Question

Today , we are going to solve an easy problem of recent codechef's programming contest .

MATBREAK

You are given a square matrix MM with NN rows (numbered 11 through NN) and NN columns (numbered 11 through NN). Initially, all the elements of this matrix are equal to AA. The matrix is broken down in NN steps (numbered 11 through NN); note that during this process, some elements of the matrix are simply marked as removed, but all elements are still indexed in the same way as in the original matrix. For each valid ii, the ii-th step consists of the following:

• Elements M1,N−i+1,M2,N−i+1,…,Mi−1,N−i+1M1,N−i+1,M2,N−i+1,…,Mi−1,N−i+1 are removed.
• Elements Mi,N−i+1,Mi,N−i+2,…,Mi,NMi,N−i+1,Mi,N−i+2,…,Mi,N are removed.
• Let's denote the product of all 2i−12i−1 elements removed in this step by pipi. Each of the remaining elements of the matrix (those which have not been removed yet) is multiplied by pipi.

Find the sum p1+p2+p3+…+pNp1+p2+p3+…+pN. Since this number could be very large, compute it modulo 109+7109+7.

Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains two space-separated integers NN and AA.

Output

For each test case, print a single line containing one integer ― the sum of products at each step modulo 109+7109+7.

Constraints

• 1≤T≤2501≤T≤250
• 1≤N≤1051≤N≤105
• 0≤A≤1090≤A≤109
• the sum of NN over all test cases does not exceed 105105

Example Input

1
3 2

Example Output

511620149

Explanation

Example case 1: 

Now , Let's look at the solution , 

The basic prerequisites for this problem are the facts 

1. a^(p-1) %p =1 for coprime a and b

2. Simple number theory and algebra

We need to solve the problem in O(logn) due to the constraints , which is achieved through the below code I have implemented.

Look at the following C code :-

#include <iostream>

using namespace std;

unsigned long long int MOD =1000000007;

unsigned long long int a;

unsigned long long int power(unsigned long long int y)  

{  

    unsigned long long int temp=0;  

    if(y == 0)  

        return 1;  

    temp = power(y / 2)%MOD;  

    if (y % 2 == 0)  

        return (temp * temp)%MOD;  

    else

    {  

        if(y > 0)  

            return (a * temp * temp)%MOD;  

    }  

}  

int main() {

    int t;

    cin>>t;

    while(t--)

    {

        long long int n;

        cin>>n;

        unsigned long long int arr[n];

        unsigned long long int ans=0,temp=0;

        long long int mod=1000000007;

        cin>>a;

        long long int i=0;

        while(i!=n)

        {

            arr[i]=((temp+1)*(2*i+1))%(p-1);

            temp=(temp+arr[i])%(p-1);

            ans=(ans+power(arr[i])%MOD)%MOD;

            i++;

           

        }

        cout<<ans<<endl;                                          

       

    }

// your code goes here

return 0;

}

The code is simply based on the pattern obtained from the numbers in the solution going step by step , and it is a solution of O(logn).

Leave any doubts in the comments .