Xor Matrix

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Let's consider a square matrix of size N × N, where N = R − L + 1. We will enumerate the columns of this matrix with consecutive integers from L to R (the leftmost column will be assigned number L and the rightmost  number R). In similar manner we will enumerate rows with the same integers (the top row will be assigned number L and the bottom row  number R).
Every cell of this matrix has an integer written inside it. The cell at the intersection of row X and column Y has integer (X xor Y) written inside.
Two cells are called adjacent if and only if they have a common side. That way every inner cell have 4 neighbors and any of four corner cells have 2 neighbors.
A walk is a sequence of cells C_{0}, C_{1}, C_{2}, ..., C_{K}, where for every 1 ≤ i ≤ K the cells C_{i1} and C_{i} are adjacent and for every 0 ≤ j ≤ K the number written inside cell C_{j} is equal j. The number K is the length of that walk.
Your task is for given L and R values, find the maximal possible value of K, as well as the count C of different walks with that maximal length. As the value of C could be very large, output it modulo (10^{9} + 7).
Input
The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows.
For each test case, the only line of input contains two integers L and R.
Output
For each test case, output a single line containing two integers K and C.
The value of C should be printed modulo (10^{9} + 7).
Constraints
 1 ≤ T ≤ 20 000
 1 ≤ L ≤ R ≤ 10^{18}
Subtasks
 Subtask #1: 1 ≤ T ≤ 500; 0 ≤ R  L ≤ 300 (8 points)
 Subtask #2: original constraints, only the value of K will be checked. (24 points)
 Subtask #3: original constraints (68 points)
Example
Input: 4 1 1 1 2 1 3 2 3 Output: 0 1 0 2 3 4 1 4
Explanation
Example case 1. The matrix contains just one cell, so, there is no possibility to make a single move, thus K = 0. We have just one possibility  to start the walk at the only cell and to end it immediately.
Example case 2. The matrix doesn't contains a cell with number one inside, so, there once again is no possibility to make a single move, thus K = 0. Our walk is just a single cell with number zero inside and there are two such cells, thus C = 2. The matrix in this case looks like this:
(1 xor 1) (1 xor 2) = 0 3 (2 xor 1) (2 xor 2) = 3 0
Example case 3. The four possible walks are:
0 3 2 0 3 2 0 3 2 0 3 2 3 0 1 3 0 1 3 0 1 3 0 1 2 1 0 2 1 0 2 1 0 2 1 0
Example case 4. The four possible walks are:
0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0
Author:  alex_2oo8 
Tester:  pushkarmishra 
Editorial  http://discuss.codechef.com/problems/XRMTRX 
Tags  adhoc, alex_2oo8, feb15, mediumhard 
Date Added:  13012015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions