## YAPP - Yet Another Permutations Problem

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 2Sample Output:2

**Constraints**

1 <= T <= 10000

1 <= N <= 1000000000

Added by: | Varun Jalan |

Date: | 2010-01-25 |

Time limit: | 1.690s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |

Resource: | own problem used for Technovanza |