# Bitwise Tuples CodeChef Solution | BITTUP

Hello coders, today we are going to solve Bitwise Tuples CodeChef Solution in C++, Java and Python.

Contents

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

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).

## Solution – Bitwise Tuples CodeChef Solution

```#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
using ll = long long int;
using namespace std;

ll getPower(ll a, ll b){
static ll mod = 1000000007;
if(b==0)return 1;
if(b==1)return a;

if(b%2==0){
ll ans = getPower(a,b/2);
return (ans * ans) % mod;
}
else {
ll ans = getPower(a,(b-1)/2);
return ((a*ans)%mod*ans)%mod;
}
}

int main() {
int t; cin >>t ;
while(t--){
ll a,b,temp;
cin >> a >> b;
temp = getPower(2,a)-1;
cout << getPower(temp,b) << endl;
}

return 0;
}
```

Disclaimer: The above Problem (Bitwise Tuples) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.

### 1 thought on “Bitwise Tuples CodeChef Solution | BITTUP”

1. java ka solution nahi hai kya bhaiya?