传送门： D.Fence Building

Farmer John owns a farm. He first builds a circle fence. Then, he will choose n points and build some straight fences connecting them. Next, he will feed a cow in each region so that cows cannot play with each other without breaking the fences. In order to feed more cows, he also wants to have as many regions as possible. However, he is busy building fences now, so he needs your help to determine what is the maximum number of cows he can feed if he chooses these n points properly.

Input

The first line contains an integer 1 \le T \le 1000001≤T≤100000, the number of test cases. For each test case, there is one line that contains an integer n. It is guaranteed that 1 \le T \le 10^51≤T≤105 and 1 \le n \le 10^{18}1≤n≤1018.

Output

For each test case, you should output a line ”Case #ii: ans” where ii is the test caseS number, starting from 11and ans is the remainder of the maximum number of cows farmer John can feed when divided by 10^9 + 7.

样例输入

3
1
3
5

样例输出

Case #1: 1
Case #2: 4
Case #3: 16

题目来源

ACM-ICPC 2017 Asia Urumqi

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const long long int mod=1e9+7;

ll mod_pow(ll x, ll n, ll p){ //快速幂 
    ll res = 1;
    while(n){
        if(n & 1) res =res * x % p;
        x = x * x % p;
        n >>= 1;
    }
    return res;
}
 
ll comb(ll n, ll m, ll p){ //comb用来求解组合数 
    if(m > n) return 0;
    ll ret = 1;
    m = min(n - m, m);
    for(int i = 1; i <= m; i ++){
        ll a = (n + i - m) % p;
        ll b = i % p;
        ret = ret * (a * mod_pow(b, p - 2, p) % p) % p;
    }
    return ret;
}
 
ll Lucas(ll n, ll m, ll p){  //卢卡斯定理---处理大的组合数对素数取模的情况，因为这时如果递推的话将会特别耗时 
    if(m == 0) return 1;
    return comb(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
 
int main(){
    int T;
    ll n, m, p;
    scanf("%d", &T);
    int cas=1;
    while(T--){
    	scanf("%lld",&n);
    	
        long long ans=(Lucas(n,2,mod)+Lucas(n,4,mod)+1)%mod;
        printf("Case #%d: %lld\n",cas++,ans);
    }
    return 0;
}