题意：N（N<=40000）个数n1, n2, ..., nN (ni<=N)，求(2 ^ n1 + 2 ^ n2 + ... + 2 ^nN) / N % 1000003。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3049

——>>RJ白书上说“因为‘乘法逆’太重要了……”，上一年南京区赛同学也碰到了求逆元……如今，学习了。。

什么是乘法逆？ab % m = 1 （这里的 a, b 分别都是模 m 的同余等价类），a 模 m 的乘法逆是 b，同一时候，b 模 m 的乘法逆是a。

乘法逆有什么用？这个用处可还真不小。。假设要求 a / b % m（保证 b | a），可是 a 非常大非常大，比方 a = 2 ^ 40000，这个式子可不等价于 (a % m) / (b % m) % m。。这时，乘法逆就能够上场了。。一个数除以 b 后模 m，等价于该数乘以 b 模 m 的乘法逆后模 m。。于是上式可变成 a * b的乘法逆 % m，这就easy多了，就是
(a % m) * (b的乘法逆 % m) % m。。

怎么求乘法逆？要求 a 模 m 的乘法逆，设其为 x，由于 a * x % m = 1，所以 a * x + m * y = 1。。这是什么，一元二次方程，于是乎，扩展欧几里得飞一下就出来了。。

#include <cstdio>

typedef long long LL;

const int MOD = 1000003;

const int MAXN = 40000 + 10;

int N, kase;

LL sum;

int pow2[MAXN];

void GetPow2()

{

    pow2[0] = 1;

    for (int i = 1; i < MAXN; ++i)

    {

        pow2[i] = (pow2[i - 1] << 1) % MOD;

    }

}

void Read()

{

    int n;

    sum = 0;

    scanf("%d", &N);

    for (int i = 0; i < N; ++i)

    {

        scanf("%d", &n);

        sum = (sum + pow2[n]) % MOD;

    }

}

void gcd(LL a, LL b, LL& d, LL& x, LL& y)

{

    if (!b)

    {

        d = a;

        x = 1;

        y = 0;

        return;

    }

    else

    {

        gcd(b, a % b, d, y, x);

        y -= a / b * x;

    }

}

LL Inv(int a, int n)

{

    LL ret, d, y;

    gcd(a, n, d, ret, y);

    return d == 1 ? (ret + n) % n : -1;

}

void Solve()

{

    LL ret;

    LL inv = Inv(N, MOD);

    ret = sum * inv % MOD;

    printf("Case %d:%I64d\n", ++kase, ret);

}

int main()

{

    int T;

    kase = 0;

    GetPow2();

    scanf("%d", &T);

    while (T--)

    {

        Read();

        Solve();

    }

    return 0;

}