AC Magic

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

bLue 最近学习了一种魔法 "AC Magic"(简称 ACM),可以把 WA (Wrong Answer) 变成 AC (Accepted)!对于一个含有 n 个评测结果的序列,bLue 可以发动魔法来使序列中相邻的两个 WA 合并成一个 AC。

作为魔法长者,bLue 拥有接近无限的魔法值,可以发动任意次数的魔法。现在他想问你,对于一个长度为 n 且全是 WA 的结果序列,bLue 最多能获得多少种结果序列?

Input

输入数据有多组(数据组数不超过 100),到 EOF 结束。

对于每组数据,输入 1 行,包含 1 个整数 n (1 <= n <= 50),表示初始全 WA 的序列长度。

Output

对于每组数据,输出 1 行,包含 1 个整数,表示答案。

Sample Input

1
2
3
5
45

Sample Output

1
2
3
8
1836311903

Hint

n = 1 时,bLue 不能发动魔法,序列只有 1 种,为 "WA"。

n = 2 时,bLue 可以选择发动 1 次魔法或不发动魔法,序列有 2 种,为 "AC" 或 "WA WA"。

n = 3 时,bLue 可以选择发动 1 次魔法或不发动魔法,序列有 3 种,为 "AC WA"、"WA AC" 或 "WA WA WA"。

Source

【2016级《程序设计基础(B)II》期末上机考试-第二场】bLue