3401：【2024年3月】3级算法等考第三题 密室机关
文件提交：无需freopen
内存限制：256 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：0
解决：0
题目描述
## Description
下图是一个密室机关的平面图，密室机关整体上是一个阶梯形状的网格区域，其中，灰色区域是陷阱，无法通行，在水平方向和竖直方向各平行铺设了n条安全暗道（蓝色线条，下图中n = 5），暗道交点处是相通的，只有蓝色暗道可以通行，而且只能向下或向右通行。密室机关中，A点是起点，B点是终点。
例如，n = 3，一共有如下5条路径（红色线条）。
给定密室机关在水平方向和竖直方向上铺设的暗道数量n，问从A 点走到B点总共有多少条不同的路径。
## Input Format
一个正整数n，表示密室机关在水平方向和竖直方向上铺设的暗道数量。
数据范围
测试点1~6：3 ≤ n ≤ 30。
测试点7~10：3 ≤ n ≤ 100。
## Output Format
一个正整数，表示从A点到B点总共有多少条不同的路径。
```input1
3
```
```output1
5
```
```input2
5
```
```output2
42
```