LOVINGPW - Loving Power

no tags 

Angel Luis is now getting math class. His teacher is teaching to him the XOR operation:

  • 0 XOR 0 = 0
  • 0 XOR 1 = 1
  • 1 XOR 0 = 1
  • 1 XOR 1 = 0

When a number has more than one bit, the operation is applied to all bits. The teacher write two numbers x, y (0 <= x, y <= N) and make the XOR operation between x and y, Angel Luis would like to know how many pairs x, y such x XOR y = 2z where z >= 0.

See that for N = 3:

  • 0 XOR 1 = 20
  • 0 XOR 2 = 21
  • 3 XOR 1 = 21
  • 2 XOR 3 = 20

So there are 4 pairs.

Given N you should return the number of pairs modulo 1000000007.

Input

First line contains number t - the number of cases. Following t lines will each have a number N.

t <= 100

N <= 1000000000000000 (1015).

Output

For each case the number of pairs modulo 1000000007.

Example

Input:
3
1
2
3

Output:
1
2
4

hide comments
Pranshul Agarwal: 2013-02-27 03:51:33

Nice question.. AC.. :)

olimpoUS: 2013-02-18 16:10:22

of course, it is done and rejudge all solution.

Aditya Pande: 2013-02-18 16:09:05

finally AC

Ehor Nechiporenko: 2013-02-18 16:09:05

To c[R]@zY f[R]0G: I am sure even on Pyramid your solution will have 0.00sec! ;-)

Last edit: 2013-02-18 11:01:58
c[R]@zY f[R]0G: 2013-02-18 16:09:05

can you change the cluster to pyramid


Added by:olimpoUS
Date:2013-02-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Luis Giro