Bitwise Tuples - Codechef Solution -| AskTheCode

June Long Challenge 2021 Solution | Bitwise Tuples Solution (BITTUP) | AskTheCode

---

Problem:

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^9+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^9+7.

---

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:

In C++ :

#include <bits/stdc++.h>
#define ll long long
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 test;
 cin >> test;
 while (test--) {
  ll a, b, temp;
  cin >> a >> b;
  temp = getPower(2 , a) - 1;
  cout << getPower(temp, b) << endl;
 }
 return 0;
}

---

In Python :

t = int(input())
mod = 1000000007
while(t):
    n,m=input().split()
    n=int(n)
    m=int(m)
    #m=int(input())
    base=(pow(2,n,mod)-1)
    print(pow(base,m,mod))
    t-=1

---

In Java :

import java.io.BufferedReader;
import java.io.*;
 class Golf2 {
    public static void main(String[] args) throws IOException {
        InputStreamReader re = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(re);
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = 0, m = 0, k = 0;
            String[] a = (br.readLine()).split(" ");
            for (int i = 0; i < a.length; i++) {
                n = Integer.parseInt(a[0]);
                m = Integer.parseInt(a[1]);
               
            }
            long mm = 1000000007;
            long  pow = 1;
            long base = 2;
            long temp=1;
            while (n > 0) {
               if (n % 2 != 0) {
                   pow=(base % mm * pow % mm)%mm;
                }
                base = (base % mm * base % mm) % mm;
                n = n / 2;
            }
            long x=pow-1;
                while (m> 0) {
               if (m% 2 != 0) {
                   temp=(temp % mm * x % mm)%mm;
                }
                x = (x % mm * x % mm) % mm;
                m = m / 2;
            }
            System.out.println(temp);
        }
    }
}