SP30739 ADADUNG - Ada and Manure

As you might know Ada the Ladybug is farmer. Last year, she sowed **N** distinct types of grain to **N** distinct places. This year she wants to seed the same types of grain again, yet there is a little problem: each type of grain needs special kind of manure, yet fertilizing soil with same kind of manure in consecutive years might destroy it. Now she is asking you to count the number of ways, to seed **N** types of grain to **N** places in such way that no type of grain will be in its original place. Since this number might be pretty big, print it modulo **10 $ ^{9} $ +7**.

The first line contains **1 , number of test-cases.** Each of following **T** lines contains **1 , number of types/places.**

For each test case, print the number of possibilities for given number of types/places modulo 1000000007.