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

Contest Page | CodeChef

(Video Editorial Link For Better Explanation)