一个n×n表a定义如下:
- 第一行和第一列包含 1,即:ai, 1 = a1, i = 1 对于所有 i = 1, 2, ..., n。
- 表中剩余的每个数字都等于其上方数字与其左侧数字之和。换句话说,其余元素由公式ai, j = ai - 1, j + ai, j - 1定义。
这些条件定义了表中的所有值。
给你一个数字 n。您需要确定上述规则定义的 n × n 表中的最大值。
输入
输入的唯一行包含一个正整数 n (1 ≤ n ≤ 10) — 表的行数和列数。
输出
打印包含正整数 m 的单行 — 表中的最大值。
示例
输入 #1
1
输出 #1
1
输入 #2
5
输出 #2
70
注意
在第二个测试中,表的行如下所示:
{1, 1, 1, 1, 1},
{1, 2, 3, 4, 5},
{1, 3, 6, 10, 15},
{1, 4, 10, 20, 35},
{1, 5, 15, 35, 70}.