UVALive 5971

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

Case 1: 1

Case 2: 3

Case 3: 53

 #include <map>

 #include <set>

 #include <list>

 #include <cmath>

 #include<cctype>

 #include <ctime>

 #include <deque>

 #include <stack>

 #include <queue>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include<climits>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define PI 3.1415926535897932626

 using namespace std;

 int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

 #define MAXN 1000005

 #define MOD 1000000007

 LL ans[MAXN],tmp[MAXN];

 void init()

 {

     ans[]=;ans[]=;

     for (int i=;i<MAXN;i++)

        {

            ans[i]=((i-)*ans[i-])+(i-)*ans[i-];

            ans[i]%=MOD;

        }

 }

 int main()

 {

     init();

     int T;int kase=;

     scanf("%d",&T);

     while (T--)

     {

         int N;

         scanf("%d",&N);

         printf("Case %d: %lld\n",kase++,ans[N]);

     }

     return ;

 }

巴特西

UVALive 5971

最新文章

热门文章