---

题目: 

pid=5363

依据前面给出的样例，得出求解公式 fn = 2^(n-1) - 1, 数据量大，实际就是求幂次方。

 

可用分治法求解。复杂度O(nlogn)

// 分治法求高速幂#include 
     
      using namespace std;typedef unsigned long long ull;const int MOD = 1000000007;ull getAns(ull a, int n){    if (n==0)        return 1;    if (n==1)        return a;    else    {        a %= MOD;        ull res = a*a;        res %= MOD;        if (n%2 == 0)        {            return getAns(res, n/2)%MOD;        }        else        {            return (getAns(res, n/2)*a)%MOD;        }    }}int main(void){    //freopen("in.txt", "r", stdin);    int t = 0;    scanf("%d", &t);    ull a = 2;    while(t--)    {        int n = 0;        scanf("%d", &n);        printf("%lld\n", getAns(a, n-1)-1);     // 2^(n-1) - 1    }    return 0;}