Series-Parallel Networks

Q10253: Series-Parallel Networks

在這個問題中，你要計算 two-terminal series-parallel network 的數量。這些東西在排列或幾何上可以視為電氣網路，就是說，不考慮關於這些連接元素的電氣特性。兩端點的其中一端可以視為頭(source)，另外一端是尾(sink)。

一個兩端點網路如果可以在以下條件產生的話，那他就是兩端點系列-平行網路：
] 一條邊是two-terminal series-parallel network。
] 如果 G₁ 和 G₂ 都是兩端點系列-平行網路，則把G₁ 和 G₂ 頭對頭，尾對尾接在一起，產生的東西也是(平行組成)。
]　如果 G₁ 和 G₂ 都是兩端點系列-平行網路，則把G₁ 的頭和 G₂ 的尾接在一起也是(系列組成)。

注意在系列-平行網路中，兩個點可以被很多條邊連接。而且，除了幾何上，如果可以交換系列間的元素使得兩個網路一致，這樣也視為相等。換句話說，系列間的交換並不會影響網路間的相等。以下三個網路是相等的：

平行的交換也不影響相等。以下三個網路也是相等的：

現在，給你 N，你要計算 N 條邊的 two-terminal series-parallel network 有幾種。例如 N = 4 時，有以下 10 個 series-parallel network：

Input

每行都有一個整數 N (1<=N<=30)，表示網路的邊數。
N = 0 表示輸入結束。

Output

對每個 N 輸出由 N 條邊構成的網路有幾種。

Sample Input	Sample Output
1 4 15 0	1 10 1399068

Translated by DarkKnight