# BITWISE TUPLES (BITTUP) Solution — Codechef JuneLong Challenge

**Problem Statement**

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 10⁹+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 10⁹+7.

# Constraints

- 1≤T≤10⁵
- 1≤N,M≤10⁶

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

**Code (Solution)**

The code has been implemented in Java

/* package codechef; // don't place package name! */import java.util.*;

import java.lang.*;

import java.io.*;/* Name of the class has to be "Main" only if the class is public. */

class Codechef

{

static long mod = 1000000007;

public static void main (String[] args) throws java.lang.Exception

{

// your code goes here

Scanner sc = new Scanner(System.in);

int t = sc.nextInt();

while(t-- > 0){

long a=0,b=0;

a = sc.nextLong();

b = sc.nextLong();

long ians = findPower(2, a)-1;

System.out.println(findPower(ians,b));

}

}

public static long findPower(long a , long b){

if(b==0)

return 1;

else if(b==1)

return a;

if((b%2)==0){

long temp = findPower(a,b/2);

return (temp*temp)%mod;

}

else{

long temp = findPower(a,(b-1)/2);

return ((a*temp)%mod*temp)%mod;

}

}

}

Hope you would have liked the article. Please give 50 claps to this article and follow me for more future programming related blogs.

**References**

(Video Editorial Link For Better Explanation)