Bitwise Tuples BITTUP SOLUTION

by

Bitwise Tuples BITTUP

Chef has two numbers N and M. Help Chef to find number of integer N-tuples (A1,A2,…,AN) such that 0≤A1,A2,…,AN≤2M−1 and A1&A2&…&AN=0, where & denotes the bitwise AND operator.

Since the number of tuples can be large, output it modulo 109+7.

Input
The first line contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains two integers N and M.
Output
For each test case, output in a single line the answer to the problem modulo 109+7.

Constraints
1≤T≤105
1≤N,M≤106
Subtasks
Subtask #1 (100 points): original constraints

Sample Input
4
1 2
2 2
4 2
8 4
Sample Output
1
9
225
228250597
Explanation
Test Case 1: The only possible tuple is (0).

Test Case 2: The tuples are (0,0), (0,1), (0,2), (0,3), (1,0), (2,0), (3,0), (1,2), (2,1).

Program:

t=int(input())
for _ in range(t):
    a,b=map(int,input().split())
    c=pow(2,a,1000000007)-1
    print(pow(c,b,1000000007))

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :