NYOJ 127星际之门(一)（Cayley定理的应用）

此定理说明用n-1条边将n个一致的顶点连接起来的连通图的个数为n^(n-2)，也可以这样理解，将n个城市连接起来的树状公路网络有n^(n-2)种方案。所谓树状，指的是用n-1条边将n个顶点构成一个连通图。当然，建造一个树状的公路网络将n个城市连接起来，应求其中长度最短、造价最省的一种，或效益最大的一种。Cayley定理只是说明可能方案的数目.

#include<iostream>
using namespace std;
#define N 10003
int main()
{
 int t,i,n;
 for(cin>>t;t--;)
 {
  cin>>n;
  int a=1,b=n-2;
  while(b)
  {
   if(b&1)
    a=a*n%N;
   b>>=1;
   n=n*n%N;
  }
  cout<<a<<endl;
 }
 return 0;
}