题目描述

如果你之前关注过HPUOJ的话，那么你一定听说过杨八方的名字。在去年，很多同学共同见证了杨八方同学的填报志愿、来到学校、军训……或许你曾陪同杨八方一起思考过许多问题，又或者你是刚听说这个名字，这都不是问题。

光阴荏苒，杨八方不见踪影已数月之久。然而，杨八方的故事还没有结束，正值第八届河南理工大学程序设计大赛开幕之际，让我们来继续关注一波杨八方的故事吧。

事实上，杨八方最近在苦恼宿舍中与室友的关系。我们知道很多宿舍都有自己的QQ群，杨八方的宿舍也不例外，六个小伙伴都在共同创建的一个QQ群中，没事聊聊天气氛也算融洽。但是，杨八方最近突然震惊的发现一个现象，她的五个室友竟然莫名其妙地共同商量好了一个事情。事情具体是什么不重要，重要的是她并没有看到室友们面对面开过什么小会议，莫非……宿舍除了共同的QQ群外还有一个五人群没加自己？

于是杨八方开始思考，假设两个人及以上便可创建一个QQ群，那么n个人的宿舍最多可能有几个不一样的QQ群呢？

输入

第一行有一个整数T，代表有T组数据。

下面T行每行是一个整数n，代表这个宿舍有n个人。

1<=T<=100000

1<=n<=1000000000

输出

对于每一个结果可能很大，所以你只需要输出对1000000007取模的结果。

样例输入

2

2

6

样例输出

1

57

---

首先对数据分析，寻找规律

当n=1时s=0；n=2时s=1；s>=3时，s=2^n-(n+1)；

由于题目要求要对1000000007取模，所以要用快速幂取模，最后减去（n-1）

注意：当上述方法求得s<0时，s=s+1000000007（因为这一点WA了8次QAQ与校赛银牌无缘(╥╯^╰╥)）

#include<stdio.h>

#include<math.h>

typedef long long ll;

ll mod_pow(ll x,ll n,ll mod)

{

    ll res=1;

    while(n>0)

    {

        if(n&1) res=res*x%mod;

        x=x*x%mod;

        n>>=1;

    }

    return res;

}

int main()

{

    int t;

    ll n,s;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%lld",&n);

        if(n==1) s=0;

        else if(n==2) s=1;

        else

        {

            s=mod_pow(2,n,1000000007)-(n+1);

            if(s<0) s+=1000000007;

        }

        printf("%lld\n",s);

    }

    return 0;

}