HackerRank Number Theory – Number of zero-xor subsets

Challenge: Number of zero-xor subsets

Subdomeniu: Number Theory (number-theory)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464739172

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/number-of-subsets/problem

Cerinta

You are given an integer $N$. Consider set $S = \{0,\ 1,\ldots ,\ 2 ^ N - 1\} $. How many subsets $A\subset S$ with $ \bigoplus_{x \in A}x = 0$ ($ \oplus $ denotes xor operation) are there?  
Print your answer modulo $(10^9 + 7)$.  
Note that the  xorsum of an empty set is zero!  

**Input Format**  
The first line contains one integer $T$, the number of testcases.  
The next $T$ lines contain one integer $N$ each.

**Output Format**  
Output $T$ lines. Each line is one number, answer to the problem modulo $10^9 + 7$.

**Constraints**  
$ 1 \le T \le 10000 $  
$ 1 \le N \le 10 ^ {18} $

**Sample Input**  

	2
    1
    2
    
**Sample Output**  

	2
    4
    
**Explanation**  
For $N = 1$ there are $2$ sets - $\varnothing$ and $\{0\}$.  
For $N = 2$ there are $4$ sets - $\varnothing$, $\{0\}$, $\{1,\ 2,\ 3\}$, $\{0,\ 1,\ 2,\ 3\}$.

Cod sursa

import sys

MOD = 1000000007
PHI = MOD - 1

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    t = int(data[0])
    out = []
    for i in range(1, t + 1):
        n = int(data[i])
        e = (pow(2, n, PHI) - (n % PHI)) % PHI
        out.append(str(pow(2, e, MOD)))
    sys.stdout.write('\n'.join(out))

if __name__ == '__main__':
    main()