← 返回题目
题库练习 上数塔
← 上一题 下一题 →

A71954 | 上数塔

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

有一个 N 层的数塔，数塔的第 i 层有 i 个位置，每个位置，可以从下一层的左下角的位置或者右下角的位置走上来。

请问从数塔的最下面一层，只能向上走，走到数塔的最上面一层，一共有多少条不同的路线？

比如：下图所示的是一个 3 层的数塔。

      1
    /   \
   2     3
 /   \ /   \
4     5     6

从最下面一层，走到最上面一层，共有 4 条不同的路线，分别是：

  1. 4 -> 2 -> 1
  2. 5 -> 2 -> 1
  3. 5 -> 3 -> 1
  4. 6 -> 3 -> 1

输入格式

输入一个整数 N，表示数塔的层数。（1 \le N \le 100）。

输出格式

输出一个整数，表示从数塔的最下面一层，只能向上走，走到数塔的最上面一层，一共有多少条不同的路线。

由于本题路线总数可能很多，请输出路线总数 \mod (10^9 + 7) 的结果。

输入输出样例

输入 #1
3
输出 #1
4
输入 #2
8
输出 #2
128
输入 #3
50
输出 #3
949480669
C++ 编辑器
输入
输出