Problem J Permutation Counting

Dexter considers a permutation of first N natural numbers good if it doesn't have x and x+1 appearing consecutively, where (1 ≤ x < N)  For example, for N=3 , all goodpermutations are:

1. {1, 3, 2}

2.{2, 1, 3}

3.{3, 2, 1}

Input

Input starts with an integer T (≤ 10000 , denoting the number of test cases.Each

case starts with a line containing an integer N (1 ≤ N ≤ 106)

.

Output

For each case, print the case number and the number ofgoodpermutations

modulo1000 000 007

.

Sample Input

Output for Sample Input

3

2

3

5

Case 1: 1

Case 2: 3

Case 3: 53

1 #include