Given a natural number N, find the number of ways in which N can be expressed as a sum of natural numbers when order is taken into consideration. Two sequences that differ in the order of their terms define different compositions of their sum.
 
Example 1:
Input: N = 2
Output: 2
Explanation: All 2 compositions are 
{1 + 1} and {2}.
Example 2:
Input: N = 4
Output: 8
Explanation: All 8 compositions are:
{1 + 1 + 1 + 1}, {1 + 1 + 2}, {1 + 2 + 1},
{2 + 1 + 1}, {2 + 2}, {1 + 3}, {3 + 1}, {4}.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function no_of_ways() which takes n as the input parameter and returns the total no. of ways modulo 10^{9} + 7.
 
Expected Time Complexity: O(log(N))
Expected Space Complexity: O(1)
Constraints:
1 <= N <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

	def no_of_ways(self, n):

		# Code here

Solutions:
class Solution:

	def no_of_ways(self, n):
		return pow(2, n - 1, 10 ** 9 + 7)


class Solution:

	def no_of_ways(self, n):
		l = [2]
		c = 1
		while c < n - 1:
			d = l[-1] * l[-1]
			l.append(d % 1000000007)
			c = c * 2
		s = bin(n - 1)
		s = s[2:]
		s = s[::-1]
		p = 1
		d = 0
		for i in s:
			if i == '1':
				p = p * l[d]
			p = p % 1000000007
			d += 1
		return p


class Solution:

	def no_of_ways(self, n):
		ans = pow(2, n - 1, 10 ** 9 + 7)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.no_of_ways(n)
		print(ans)