I can't remember the name of the problem. But here is the problem description.

Given a positive integers n <= 10^5, a, b. Find a^{F(n)*b} mod M where

F(n)=C(n,0)^2+C(n,1)^2+...+C(n,n)^2

where C(n,k) is the number of ways to choose k distinct objects from n distinct objects and M=10^9+7.

First, we need to find F(n) in a closed form in order to avoid TLE. Because generating C(n,k) needs O(n) time.

We can write the sum as this:

F(n)=C(n,0)*C(n,n)+C(n,1)*C(n,n-1)+...+C(n,n)*C(n,0)

because C(n,k)=C(n,n-k) as we know. What does C(n,i)*C(n,n-i) mean? Think clearly. It means you have to choose i persons from n in C(n,i) ways and once again C(n,n-i) means you can choose n-i persons from n persons. Together what can we say?

If there are 2n persons in a pool, in how many ways can you choose n of them? In C(2n, n) ways. On the other hand, think this way. Divide them into two parts, each having n persons. Now, if you choose i persons from the n of the first pool, you have to choose n-i others from the second. Thus together you can have C(n,i)*C(n,n-i) choices. Since i can run from 0 to n, we have that

C(n,0)*C(n,n)+C(n,1)*C(n,n-1)+...+C(n,n)*C(n,0) = C(2n, n)

Thus, F(n)=C(2n,n). Now we have narrowed it down. We only need a^{C(2n,n)*b}%M.

We can use Fermat's Little Theorem. You have to find the remainder of C(2n,n)*b upon division by M-1. But how would you calculate C(2n,n)? You can try with the primes less than or equal to n and how many times they occur(You have to use Legendre's Theorem).

But I already got TLE using this method. So we need another idea. I don't know what the author's solution is, but here is what I did.

From previous experience, I knew that for M=10^9+7, N=(M-1)/2=5*10^8+3 is a prime. Also, from the identity,

k*C(n,k) = n*C(n-1,k-1)

we need that, C(2n,n)=2C(2n-1,n-1)%2N with N a prime. Then

C(2n,n)%2n=2*C(2n-1,n-1)%2N

We can invoke Extended Euclidean Algorithm

C(n,k)=n!/(k!*(n-k)!)

So if 2n is co-prime with k! and (n-k)!, we can find the modular inverses of them modulo 2n. There lies the main problem. 2n is not co-prime with k! of (n-k)!. They share 2 as a common factor. If we can rule out 2, then we can find the remainder with Extended_Euclid. The previous identity lets us use this fact.

We shall find the remainder of C(2n-1,n-1) upon division by N. If we find

C(2n-1,n-1)%N=r

then C(2n,n)%2n=2*r%(2N). Store the values of n! modulo M upto n=10^5. Then use EEA to find their modular inverses. Then use fast modular exponentiation.

Once one of my friend told that, he heard from someone else-"Every problem from SpOJ needs a different algorithm to get an ac." I guess he is right!!