Counting is life

All submissions for this problem are available.
You are given a set $S$ of $K$ numbers which is a set of first $K$ powers of $2$ (ie. $1$,$2$,$4$,$8$,...) Given $N$ you have to construct an Array $A$[$0$, ..., $N1$] of length $N$ such that $A[i]$ must belong to $S$ for all $i$, $0$ <= $i$ < $N$. Find the maximum value of $A[0]$ XOR $A[1]$ XOR ... XOR $A[N1]$ that you can achieve. Here XOR is bitwise xor operator. Also, tell the number of arrays $A$ that gives this maximum XOR. Print both the numbers mod $10^9+7$. ###Input:  First line of Input contains the no of test cases T.  Each of the next T lines contains two integers: N and K. ###Output:  For every test case, print two spaceseparated integers: maximum possible XOR and the no of possible ways respectively, modulo $10^9+7$. ###Constraints  $1\leq T \leq 100000$  $1\leq N \leq 10^9+7$  $1\leq K \leq 100000$  $K \leq N$  Sum of $K$ over all testcases $\leq 1000000$ ###Sample Input: 1 3 3 ###Sample Output: 7 6 ###Explanation: Here $S = {1,2,4}$ Then max xor is $1$ xor $2$ xor $4 = 7$ Number of $A = $ all permutation of $[1,2,4] = 6$ Therefore the output would be 7 6.Author:  kr_abhinav 
Editorial  https://discuss.codechef.com/problems/CNTL 
Tags  codemelange, combinatorics, hard, kr_abhinav, math 
Date Added:  1042018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 