#P14107. 【动态规划2】二维矩阵路线方案数问题

【动态规划2】二维矩阵路线方案数问题

题目描述

给定一个大小为 n×nn \times n 的二维矩阵,计算从起点 (1,1)(1, 1) 到终点 (n,n)(n, n) 的所有可能路径的数量。每一步可以向右或向下移动一个格子。

输入

输入包含一个整数 nn,表示矩阵的大小。 1<=n<=171<=n<=17

输出

输出一个整数,表示从 (1,1)(1, 1)(n,n)(n, n) 的路径总数。

示例

输入

输出

说明

3×33 \times 3 的矩阵中,从 (1,1)(1, 1)(3,3)(3, 3) 的路径共有 66 种可能。