A magic number is defined as a number that can be expressed as a power of 5 or sum of unique powers of 5. First few magic numbers are 5, 25, 30(5 + 25), 125, 130(125 + 5), ….
Given the value of n, find the n'th Magic number modulo 10^{9}+7.
Example 1:
Input: n = 1
Output: 5
Explanation: 1'st Magic number is 5.
Ã¢â¬â¹Example 2:
Input: n = 2
Output: 25
Explanation: 2'nd Magic number is 25. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function nthMagicNo() which takes n input and returns the answer.
Expected Time Complexity: O(log n)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def nthMagicNo (self, n):
        #complete the function here

Solutions:
class Solution:

	def nthMagicNo(self, n):
		p = 5
		magic = 0
		while n:
			if n % 2 == 1:
				magic += p
			p *= 5
			n //= 2
		return magic % 1000000007


class Solution:

	def nthMagicNo(self, n):
		mod = 10 ** 9 + 7
		p = 1
		ans = 0
		while n != 0:
			p *= 5
			if n % 2 == 1:
				ans = (ans + p) % mod
			n = n // 2
		return ans % mod


class Solution:

	def nthMagicNo(self, n):
		(res, x, m) = (0, 5, 10 ** 9 + 7)
		while n != 0:
			if n % 2 == 1:
				res += x
			x = x * 5
			n = n >> 1
		return res % m


class Solution:

	def nthMagicNo(self, n):
		mod = 1000000007
		p = 1
		ans = 0
		while n != 0:
			p *= 5
			if n % 2 == 1:
				ans = (ans + p) % mod
			n //= 2
		return ans % mod


class Solution:

	def nthMagicNo(self, n):
		m = 10 ** 9 + 7
		p = 1
		a = 0
		while n:
			p *= 5
			if n % 2 == 1:
				a = (a + p) % m
			n = n // 2
		return a % m


class Solution:

	def nthMagicNo(self, n):
		s = 0
		i = 1
		while n:
			if n & 1:
				s += 5 ** i
			n = n >> 1
			i += 1
		return s % (10 ** 9 + 7)


class Solution:

	def nthMagicNo(self, n):
		ans = 0
		base = 5
		while n > 0:
			last = n & 1
			n = n >> 1
			ans += last * base
			base = base * 5
		return ans % (10 ** 9 + 7)


class Solution:

	def nthMagicNo(self, n):

		def binary(n):
			if n <= 1:
				return str(n)
			return str(n % 2) + binary(n // 2)
		x = binary(n)
		ans = 0
		mul = 1
		for i in x:
			mul *= 5
			ans += mul * int(i)
		return ans % (10 ** 9 + 7)


class Solution:

	def nthMagicNo(self, n):
		if n == 1:
			return 5
		n = bin(n).replace('0b', '')[::-1]
		ans = 0
		for i in range(1, len(n) + 1):
			ans += 5 ** i * int(n[i - 1])
		return ans % (10 ** 9 + 7)


class Solution:

	def nthMagicNo(self, n):
		p = 1
		a = 0
		while n != 0:
			p *= 5
			if n % 2 == 1:
				a = (a + p) % 1000000007
			n = n // 2
		return a % 1000000007
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthMagicNo(n))


class Solution:

	def nthMagicNo(self, n):
		mod = 10 ** 9 + 7
		p = 1
		ans = 0
		while n != 0:
			p *= 5
			if n % 2 == 1:
				ans = (ans + p) % mod
			n = n // 2
		return ans % mod
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nthMagicNo(n))


class Solution:

	def nthMagicNo(self, n):
		res = 0
		temp = 1
		while n != 0:
			temp = temp * 5
			if n % 2 == 1:
				res = res + temp
			n = n // 2
		return res % 1000000007


class Solution:

	def nthMagicNo(self, n):
		b = bin(n)[2:][::-1]
		s = 0
		for i in range(len(b)):
			if b[i] == '1':
				po = 5 ** (i + 1)
			else:
				po = 0
			s = s + po % 1000000007
		return s % 1000000007


import math

class Solution:

	def nthMagicNo(self, n):
		s = 0
		i = 1
		while n > 0:
			if n % 2 == 1:
				s += math.pow(5, i) % (math.pow(10, 9) + 7)
			i += 1
			n //= 2
		return int(s % (math.pow(10, 9) + 7))


class Solution:

	def nthMagicNo(self, n):
		s = bin(n).replace('b', '')
		s = s[::-1]
		ans = 0
		for i in range(len(s)):
			ans += 5 ** (i + 1) * int(s[i])
		ans = ans % (10 ** 9 + 7)
		return ans


class Solution:

	def nthMagicNo(self, n):
		val = 0
		i = 1
		while n > 0:
			i *= 5
			if n & 1:
				val += i
			n >>= 1
		return val % 1000000007