[BZOJ2467] [中山市选2010]生成树

Description

有一种图形叫做五角形圈。一个五角形圈的中心有1个由n个顶点和n条边组成的圈。在中心的这个n边圈的每一条边同时也是某一个五角形的一条边，一共有n个不同的五角形。这些五角形只在五角形圈的中心的圈上有公共的顶点。如图0所示是一个4-五角形圈。

现在给定一个n五角形圈，你的任务就是求出n五角形圈的不同生成树的数目。还记得什么是图的生成树吗？一个图的生成树是保留原图的所有顶点以及顶点的数目减去一这么多条边,从而生成的一棵树。

注意：在给定的n五角形圈中所有顶点均视为不同的顶点。

Input

输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组测试数据包含一个整数n( 2<=N<=100)，代表你需要求解的五角形圈中心的边数。

Output

对每一组测试数据，输出一行包含一个整数x，表示n五角形圈的生成树数目模2007之后的结果。

Sample Input

1
2

Sample Output

记得这题是高一寒假讲的？

那时候我什么都不会，上课不是在颓废就是在睡觉。

我记得苏卿念同学上去切了这道题Orz。

现在看来的确很水...

我们发现要想它成为一棵树，每个五边形必须切一次，切必须在中间的环上切至少一次。

所以答案就是$n imes 4 imes 5^{n-1}$。

就是切中间的环有$n$种切法，切掉的那一边对应的五边形有4种切法，剩下的都有5种切法。

诶，马上要退役了，感慨万分，当时为什么不好好学呢...

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll T, n;
#define mod 2007
ll ksm(ll x, ll y) {
    ll res = 1;
    while(y)
    {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

int main()
{
    cin >> T;
    while(T--)
    {
        scanf("%lld", &n);
        printf("%lld
", n * 4 % mod * ksm(5, n - 1) % mod);
    }
    return 0;
}