Description

下图是一个密室机关的平面图，密室机关整体上是一个阶梯形状的网格区域，其中，灰色区域是陷阱，无法通行，在水平方向和竖直方向各平行铺设了n条安全暗道（蓝色线条，下图中n=5），暗道交点处是相通的，只有蓝色暗道可以通行，而且只能向下或向右通行。密室机关中，A点是起点，B点是终点。

给定密室机关在水平方向和竖直方向上铺设的暗道数量n，问从A点走到B店总共有多少条不同的路径。

Format

Input

一个正整数n，表示密室机关在水平方向和竖直方向上铺设的暗道数量。

数据范围 测试点1~6：3<=n<=30。 测试点7~10：3<=n<=100。

Output

一个正整数，表示从A点到B点总共有多少条不同的路径。

Samples

3

5

5

42

Limitation

1s, 1024KiB for each test case.