LOVEBIRDS - She was in Love with BST


Devo! She has broken up with him again!Frown

And after a series of break ups and patch ups , she is done with him!

Being a geek to keep herself distracted, she picks up her favourite topic of dynamic programming where she comes across this idiot problem which says

Given a integer N , you have to tell the sum of number of structurally unique Binary search trees built on different permutations of the set{x , x such  that x belongs to [1,N] and x is an integer}.

A Binary Search tree is said to be built on a permutation iff the in-order traversal of that BST is same as the permutation. 

A permutation is said to be distinct from another  if there exists a position i such that the i th  element of both the permutations is different. 

Now, her inability to solve the problem is quite stressful to her! Help her in Solving the problem!  

NOTE: She observes that this number can be very large so output this number Modulo 1908 .

Moreover she tells you that there in-order traversal of a Binary search tree is Unique. 

For Binary Search Tree Read https://en.wikipedia.org/wiki/Binary_search_tree

Input

The first line of the input consists of T , the number of test cases.

The following T lines consists of a single integer N 

(N can be at max 1000 , T can be at max 1000)

Output 

You have to Output T lines each consisting of the answer to the problem Modulo 1908

Example

Input:
2
1
2

Output:
1
2

hide comments
surajxd: 2020-08-30 10:28:03

catalan number..

kushrike: 2020-05-22 23:54:55

No need of catalan numbers. Just visualise the BST when node 'i' is the root. Rest is simple P & C.

raipavitra: 2020-02-16 17:43:33

simple p and c with recurrence.
no need to think about nth catalan numbers.

aman_sachin200: 2018-06-15 22:59:26

Awesome One!!!No need to know Catalan Numbers....form a recurrence and then its pretty easy to solve..loved solving it!!!! :P

mahilewets: 2017-09-13 22:18:03

I have forgot formula for Catalan numbers
Remember there are some (2N)!, N!, some N
So I did it by dynamic programming
It was fun

heisenberg0820: 2017-06-23 11:33:19

@aman_9899 Pro _/\_

aman_9899: 2017-06-20 21:00:59

hint : catalan numbers...!!!

steady_bunny: 2017-06-09 07:54:38

May be Catalan numbers will be useful have a look on them!!!

maverick_10: 2015-12-10 00:00:27

Did this in 0.02sec feeling very great!!!
A good question it was. Idea came from optimal binary search trees.

Aman Kumar: 2015-08-19 11:18:27

how is the answer for 2 is 2 ?
1
2
1 2
shouldn't it be 3 ? if 1 and 2 are considered structurally same , shouldn't the answer for n be n only ?


EDIT(psych_cod3r)=>
No, we can form different structures from the same permutations!

Last edit: 2015-08-20 13:15:43

Added by:psych_cod3r
Date:2015-08-17
Time limit:1s
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 MAWK BC NCSHARP COFFEE DART FORTH GOSU JS-MONKEY JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA
Resource:Intuition