ADV04B1  Upper Right King (Hard)
There is a king in the lower left corner of the n × n checkmate board. The king can move one step right, one step up or one step upright. How many ways are there for him to reach the upper right corner of the board?
Input
The first line of input contains number T  the amount of test cases. Next T lines consist of single integer n  the size of the board.
Constraints
1 <= T <= 10000
1 <= n <= 1000000
Output
For each test case output the munber of ways to reach upper right corner of n × n board modulo 1000003.
Example
Input: 2 2 3 Output: 3 13
hide comments
bashrc is back:
20121027 13:49:02
@shubhang try reducing the mod operations. 

shubhang singh chauhan:
20120721 09:01:49
@Tjandra Satria Gunawan thats what i am doing but still tle.I have also posted on forum recently, if u can take a look at my code there . 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120721 08:53:56
@shubhang singh chauhan: after precomputation it's possible to make O(1) time ;) 

shubhang singh chauhan:
20120721 06:41:48
@spooky i am getting tle ... complexity of my code is O(nlogn) where n is 10^6.I am doing precomputation. plz check my solution id=7350980. 

Yatindra:
20110826 15:18:42
*>><<* Last edit: 20110826 15:19:06 

Spooky:
20110429 07:44:42
it should for sure 

.:
20110428 17:39:01
Should the time complexity be better than O(n^2)? 
Added by:  Spooky 
Date:  20101114 
Time limit:  1.183s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Advancement Autumn 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin 