Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0192 - CATALAN SQUARE

 

Last weekend you and your friends went to visit the local farmer’s market at the town square. As you were standing around in a circle talking, you couldn’t help overhearing two of your friends musing over what sounded like an interesting problem: They were consid- ering the number of ways in which you could all shake hands, such that everyone in the circle simultaneously shaked hands with one other person, but where no arms crossed each other.

After a few seconds’ thought you decided to join your two friends, to share (with them) the solution to their problem. “If we are 2n persons”, you said, “pick any particular person, and let that person shake hands with somebody. That person will have to leave an even number of people on each side of the person with whom he/she shakes hands. Of the remaining n 1 pairs of people, he/she can leave zero on the right and n 1 pairs on the left, 1 on the right and n 2 pairs on the left, and so on. The pairs remaining on the right and left can independently choose any of the possible non-crossing handshake patterns, so the count Cn for n pairs of people is given by:

Cn = Cn1C0 + Cn2C1 + . . . + C1Cn2 + C0Cn1,

which, together with the fact that C0 = C1 = 1, is just the definition of the Catalan numbers.” By consulting your handy combinatorics book, you find out that there is a much more efficient formula for calculating Cn, namely:

 

After a collective groan from the group, your particularly cheeky friend Val called out “Well, since we are at the town square, why don’t you try to square your Catalan numbers!”. This was met with much rejoicing, while you started to think about how to square the Catalan sequence. . .

 

Task

Let Cn be the nth Catalan number as defined above. By regarding the sequence (Cn)n0 of Catalan numbers, we can define a sequence (Sn)n0, corresponding to “squaring the Catalan sequence”, by considering the Cauchy product, or discrete convolution, of (Cn)n0 with itself, i.e.,

 

 Your task is to write a program for calculating the number Sn. 

Input

The input contains one line containing one non-negative integer: n, with 0 n 5 000.

Output

Output a line containing Sn.

Examples

stdin

stdout

1

 0

1

2

 59

1583850964596120042686772779038896


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Nordic (NCPC) 2014.C

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.