MCIRGAME - Point Connection Game in a Circle

This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, . . . , 2n − 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect. It’s still a simple game, isn’t it? But after you’ve written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right!

Input

Each line of the input file will be a single positive number n, except the last line, which is a number −1. You may assume that 1 ≤ n ≤ 150.

Output

For each n, print in a single line the number of ways to connect the 2n numbers into pairs.

Sample

Input
2
-1

Output
2
Note : Big num!

Được gửi lên bởi:psetter
Ngày:2009-02-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Pre Shanghai 2004

hide comments
2015-06-24 04:18:58 N�ng D�n John
Chủ yếu là BigNum
2015-06-24 04:18:37 N�ng D�n John
Chuû yeâu laø Bignum
2014-06-26 11:20:33 Thcs Ðặng Chánh Kỷ
Code số lớn mệt thật , ns chung là dễ
2013-08-14 11:53:22 Pham Dat
phải gọi là đoạn thẳng nối 2 điểm thôi chứ
2013-08-08 03:39:08 John and the cows
150 ra 28336159511286454919521412986993508946492467649011644182088598624691519032559650708037365499927532029654393447069621322187712454333678323104526897225807029224162563399190436400 phải không nhỉ??? xem mình làm bị kết quả sai ???
2011-12-24 02:04:18 kệ anh chứ
bài này dùng catalan à
2011-06-17 09:07:11 trandatbav
Bài dễ quá, còn bài nào không ạ
2010-02-25 16:12:28 lee
difficult. i cant find out any solution
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.