プログラミングの美2014資格試合テーマ2:大神と3人の仲間

時間制限:2000 ms
単点時間:1000 ms
メモリ制限:256 MB
説明
L国は美しい景色があり、物産が豊富な国で、多くの人がここに旅行に来るのが好きで、記念品を持って行くのが好きで、大神さんも例外ではありません.L国を開く時間はますます近くなって、大神さんは彼女のかわいい仲間たちにどんな記念品を持っていくのがいいか悩んでいます.今、大神さんの前に並んでいるのは3種類の記念品A、B、Cが選べます.それぞれの記念品はN種類あります.そのうち種類はA_i, B_i, C_iの記念品の価値はいずれもiであり、それぞれN+1-i個が残っている.今、大神さんは3種類の記念品の中で1つずつ選んで、かわいい3人の仲間に贈りたいと思っていますが、彼女はちょうど2つの価値の同じ記念品を選ぶことを望んでいません.このように同じ価値の記念品を手に入れた2人の仲間は、大神が別の仲間をかばって1週間以上相手にしないと思っています.今、大神さんはあなたが買った3つの記念品が3人の仲間を喜ばせ、彼女とけんかしないことを望んでいます.彼女は全部で何種類の異なる選択方法があるか知りたいと思っています.
案数が非常に大きいかもしれないので、大神さんは記念品を選ぶ案を知りたいと思っています.
 
入力
第1行は、データのグループ数を表す数Tを含む.
次に、整数Nを含むT組のデータが含まれ、各組のデータは1行ずつ含まれる.
 
しゅつりょく
各グループのデータについて、1行の「Case x:」を出力し、xは各グループのデータの番号(1から)を表し、次の数を表し、型10^9+7後の選択記念品の案数を表す.
 
データ範囲
小さいデータ:
1<=T<=10
1<=N<=100
ビッグデータ:
1<=T<=1000
1<=N<=10^18
 
サンプル解釈
第2グループのデータについて、合法的な案は以下のいくつかあり、(X,Y,Z)はA類記念品の中でXの価値があり、B類記念品の中でYの価値があり、C類記念品の中でZの価値があることを示している.
(1,1,1):3*3*3=27種
(1,2,3):3*2*1=6種
(1,3,2):3*1*2=6種
(2,1,3):2*3*1=6種
(2,2,2):2*2*2=8種
(2,3,1):2*1*3=6種
(3,1,2):1*3*2=6種
(3,2,1):1*2*3=6種
(3,3,3):1*1*1=1種
全部で27+6+6+6+8+6+6+6+6+1=72種類の記念品を選ぶ案
(1,1,2)、(2,3,3)、(3,1,3)のように、同じ価値の記念品が2つ適切に選択されているため、要求に合致する記念品の選択方法ではないことに注意してください.
 
 
 
サンプル入力

2
1
3

サンプル出力

Case 1: 1
Case 2: 72

      

//source here
#include <stdio.h>


int main()
{
    int T,n;
    int i,j,k,l;
    int all;
    int txxx=0;
    int tmp=1000000007;
    scanf("%d",&T);

    for(l=0; l <T; l++)
    {
        scanf("%d",&n);
        all=0;
        for(i=1; i<=n; i++){
            all=all+(n+1-i)*(n+1-i)*(n+1-i);
        }
        for(i=1; i<=n; i++){

            for(j=1; j<=n; j++){
                if(i==j)continue;
                for(k=1; k<=n; k++)
                {
                    if(k==j || k==i)continue;
                    txxx=(n+1-i)*(n+1-j)*(n+1-k);
                    all+=txxx;
                    all=all%tmp;
                }
            }
        }

        printf("Case %d: %d
",l+1,all);
    }
    return 0;
}