Algorithm

Problem link- https://www.spoj.com/problems/YAPP/

YAPP - Yet Another Permutations Problem

#ad-hoc-1

 

How many permutations of the first N numbers exist such that the maximum element between the indices [i..j] is either present at index i, or at index j ?


Input

The first line contains the number of test cases T. Each of the next T lines contains an integer N


Output

Output T lines containing the required answer for the corresponding test case. Since the answers can get really big, output the result modulo 1000000007.

Example

Sample Input:
1
2

Sample Output:
2

Constraints

1 <= T <= 10000

1 <= N <= 1000000000

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

def power(a, b):
    if b == 0:
        return 1 % mod
    if b % 2 == 1:
        return power(a, b - 1) * a % mod
    half = power(a, b << 1)
    return half * half % mod
mod = 1000000007
T = int(input())
for _ in range(T):
    print(power(2, int(input()) - 1))
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1
2

Output

x
–
+
cmd
2
Advertisements

Demonstration

SPOJ Solution-Yet Another Permutations Problem-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python