lucky-numbers-20

Golu wants to find out the sum of Lucky numbers.Lucky numbers are those numbers which contain exactly two set bits.This task is very diffcult for him.So Help Golu to find sum of those numbers which exactly contain two set bits upto a given number N.

3 5 10 are lucky numbers where 7 14 are not.

INPUT First line contain number of test cases T.Each test case contains a single number N.
OUTPUT Print sum of all Lucky Numbers upto N.Output may be large so take modulo with 1000000007.  
Constraints 

1 ≤ T ≤ 10^5
1 ≤ N ≤ 10^18

NOTE: Since value of test cases and n is really large, please use fast I/O optimization techniques. 

SAMPLE INPUT
1
5

SAMPLE OUTPUT
8

Difficulty: EASY

Starter code:

Solutions:
import sys
bits = [2**e for e in range(64)]
lucky = [-1]
prefix_sum = [0]
for i in range(1, 64):
	base = bits[i]
	for j in range(i):
		lucky.append(base + bits[j])
		prefix_sum.append((prefix_sum[-1] + lucky[-1])%1000000007)

t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	start = 0
	end = len(lucky)-1
	while start <= end:
		mid = start + (end-start)/2
		if lucky[mid] <= n and lucky[mid+1] > n:
			print(prefix_sum[mid])
			break
		if lucky[mid] > n:
			end = mid-1
		else:
			start = mid+1


import math

mod = 1000000007

def ans_of_last_set_bit(a, b):
	ans1 = (int(math.pow(2, b)) - 1) % mod
	ans2 = (int(math.pow(2, a - 1)) * b) % mod
	# print ans1, ans2
	return (ans1 + ans2) % mod

t = int(input())
for i in range(t):
	n = int(input())
	if n == 1 or n == 2:
		print("0")
	else:
		if math.log(n, 2) == int(math.log(n, 2)):
			n -= 1
		j, last, seclast, ans = 1, -1, -1, 0
		while n:
			if n & 1 == 1:
				seclast = last
				last = j
				# print last, seclast
			n >>= 1
			j += 1
		while seclast:
			ans = (ans + ans_of_last_set_bit(last, seclast)) % mod
			last -= 1
			seclast = last - 1
		print(ans)


import math, bisect
temp , a , b , A , F = 1, [], [], [], {}
while temp < 10**20:
	a.append(temp)
	temp=temp*2
for i in range(len(a)):
	for j in range(i+1,len(a)):
		b.append(a[i] + a[j])
b = sorted(b)
for i in range(len(b)):
	if(i==0): A.append(b[i])
	else: A.append(A[i-1] + b[i])
#	print A[i]
for _ in range(eval(input())):
	x = eval(input())
	if x < 3: print(0)
	else: print(A[bisect.bisect(b,x) - 1]%(10**9 + 7))



__author__ = 'legion'

from sys import stdin, stdout
import itertools

def kbits(n, k):
	result = []
	for bits in itertools.combinations(list(range(n)), k):
		s = ['0'] * n
		for bit in bits:
			s[bit] = '1'
		s = int((''.join(s)), 2)
		result.append(s)
	return create_dict(result)


def create_dict(result):
	set_bits_sum = dict()
	set_bits_sum[result[len(result) - 1]] = result[len(result) - 1]
	i = len(result) - 2
	while i >= 0:
		set_bits_sum[result[i]] = (set_bits_sum[result[i + 1]] + result[i]) % (10 ** 9 + 7)
		i -= 1
	return set_bits_sum


def is_power2(num):
	return ((num & (num - 1)) == 0) and num > 0


def nearest_key(key):
	if is_power2(key):
		return (3 * key) / 4
	else:
		binary_no = "{0:b}".format(key)
		split_list = list(binary_no)
		i = 0
		counter = 0
		while i < len(split_list):
			if (counter != 2) and (split_list[i] == '1'):
				counter += 1
			elif counter == 2:
				split_list[i] = '0'
			i += 1
		return int((''.join(split_list)), 2)


set_dict_keys = kbits(63, 2)

iteration = int(stdin.readline())
for num in range(iteration):
	input_no = int(stdin.readline())
	if input_no < 3:
		stdout.write(str(0) + "\n")
	else:
		stdout.write(str(set_dict_keys[nearest_key(input_no)]) + "\n")


t = 60 * [0]
for i in range(2, 60):
	x = 1 << (i-1)
	t[i] = x * (i-1) + 2**(i-1) - 1 + t[i-1]
from math import log    
for _ in range(int(input())):
	n = int(input())
	f = int(log(n, 2))
	ans = t[f]
	b = 2 ** f
	n -= b
	if n > 0:
		g = int(log(n, 2)) + 1
		ans += b*g + 2**g-1
	print(ans % 1000000007)


for _ in range(eval(input())):
	n = eval(input())
	b_n = bin(n)
	lim = len(b_n) - 2
	s = 0
	try:
		q = b_n[3:].index('1') + 1
		for j in range(0, q):
			s -= 2**(lim - 1) + 2**(lim - j - 1)
		s += 2**(lim - 1) + 2**(lim - 1)
	except:
		for j in range(1, lim):
			s -= 2**(lim - 1) + 2**(lim - j - 1)
	for i in range(lim - 1):
		s += (lim - i - 1) * 2**(lim - i - 1)
	s += 2**lim - lim - 1
	s = s % 1000000007
	print(s) 


MOD = 1000000007
t = int(input())
def rbit(n):
	count = 0
	while n>0:
		n = n>>1
		count += 1
	return count

while t>0:
	t = t- 1
	n = int(input())
	x = rbit(n)
	multiplier = x-2
	size = x-1
	temp = 0
	for i in range(size):
			temp = (temp<<1)|1
	s = (temp*multiplier)%MOD
	temp = 1<<(x-1)
	z = 0
	for i in range(x-1):
		z = temp + (1<<i)
		if z <= n:
			s = (s+ z)%MOD
	print(s)


arr=[1]
i,j,t=0,0,2
art=[]
sumarr=[]

def binarysearch(a,t):
	low=0
	high=len(a)-1
	while low<=high:
		mid=(low+high)/2
		if t==a[mid]:
			#print mid
			return mid+1
		elif t<a[mid]:
			high=mid-1
		else:
			low=mid+1
	
	if a[mid]<t:
		return mid+1
	else:
		return mid
#powers of 2 array
for i in range(60):
	arr.append(t)
	t=t*2

#lucky numbers array
i=0
while i<len(arr):
	j=0
	while j<i:
		art.append(arr[i]+arr[j])
		#print arr[i],arr[j]
		j+=1
	i+=1

#sum of lucky numbers array
temp=0
for item in art:
	temp+=item
	sumarr.append(temp)
#print sumarr[:20]
#print art[:20]
for _ in range(eval(input())):
	n=eval(input())
	if n==1 or n==2:
		print(0)
	else:
		x=binarysearch(art,n)-1
		#print n,
		#print x,
		
		print(sumarr[x]%1000000007)