ADV04B1 - Upper Right King (Hard)

no tags 

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 up-right. 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: 2012-10-27 13:49:02

@shubhang try reducing the mod operations.

shubhang singh chauhan: 2012-07-21 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)(曾毅昆): 2012-07-21 08:53:56

@shubhang singh chauhan: after precomputation it's possible to make O(1) time ;)

shubhang singh chauhan: 2012-07-21 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: 2011-08-26 15:18:42

*>><<*

Last edit: 2011-08-26 15:19:06
Spooky: 2011-04-29 07:44:42

it should for sure

.: 2011-04-28 17:39:01

Should the time complexity be better than O(n^2)?


Added by:Spooky
Date:2010-11-14
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