Square It Up

Problem code: AD5

All submissions for this problem are available.

A square piece of paper with integer dimensions NxN is placed with a corner at the origin and two of its sides along the x- and y-axes. Then, we cut it up respecting the following rules:

1.We only make straight cuts between two points lying on different sides of the square, and having integer coordinates.

2.Two cuts cannot cross, but several cuts can meet at the same border point.

3.Proceed until no more legal cuts can be made.

Counting any reflections or rotations as distinct, we call C(N) the number of ways to cut an NxN square.

Input

First line contains the number of test cases t(1<=t<=1000) and followed by t lines which contain various values of n(1<=n<=330).

Output

For each value of n, print value of C(n) MOD (10^8)

Example

Input:
2
1
2

Output:
2
30

Explanation
For n=2, answer is

Date: 2010-02-28
Time limit: 2s
Source limit: 50000
Languages: C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS


Comments

All the participants may post

nirley.gupta @ 4 Mar 2010 07:04 PM

All the participants may post their doubts in the comments section under the Rules and Regulation of this section or mail it to algothika.algochallenge@gmail.com

ALGOTHIKA ORGANIZER

NIRLEY GUPTA

Join us also on

nirley.gupta @ 4 Mar 2010 08:40 PM

Join us also on facebook

ALGOTHIKA

Please post all your doubts

nirley.gupta @ 4 Mar 2010 08:46 PM

Please post all your doubts here or mail it to algothika.algochallenge@gmail.com

ALGOTHIKA ORGANIZER

Nirley Gupta

Are you sure with the time

mcsharma1990 @ 5 Mar 2010 06:46 PM

Are you sure with the time limit?

@Mahesh yes.....

nirley.gupta @ 5 Mar 2010 08:48 PM

@Mahesh

yes.....

@Nirley can u tell the ans

vish @ 9 Mar 2010 12:56 PM

@Nirley

can u tell the ans for n=3

@soc For n=3 answer is 604

nirley.gupta @ 9 Mar 2010 07:06 PM

@soc

For n=3 answer is 604

Looking at the number of

nirley.gupta @ 10 Mar 2010 11:30 PM

Looking at the number of solutions in this problem....

The value of t has been reduced to 20...

so 1<=t<=20............

 

Please make that change.........

Please give me some real

nirley.gupta @ 10 Mar 2010 11:39 PM

Please give me some real solutions for this, as you will be evaluated for the algorithm used.....

can anybody explain the algo

dabbcomputers @ 19 Mar 2010 11:25 PM

can anybody explain the algo behind this problem...???thanx

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions