从第一列任意起点出发的走法

题目描述

在一张大小为 $n \times m$ 的棋盘上，行从上到下编号为 $1 \sim n$，列从左到右编号为 $1 \sim m$。
现在可以从第一列任意一行的格子作为起点出发，即起点可以是 $(1,1),(2,1),\dots,(n,1)$ 中的任意一个。

从某个起点出发，卒每一步必须向右侧移动一列，但行号可以变化：

• 可以走到右上方：$(i,j) \rightarrow (i-1,j+1)$；
• 可以走到正右方：$(i,j) \rightarrow (i,j+1)$；
• 可以走到右下方：$(i,j) \rightarrow (i+1,j+1)$；

如果目标格子不在棋盘范围内，则不能走这一步（例如在最上面一行就不能往右上走）。

路径的终点必须在最后一列，即 $(1,m),(2,m),\dots,(n,m)$ 中的任意一个。
从第一列任意起点出发，到最后一列任意终点结束，每一条合法路径都只允许按上面的规则移动。

请你计算：一共有多少条不同的路径。

输入格式

输入只有一行，包含两个整数 $n,m$，表示棋盘的行数和列数。

输出格式

输出一行，一个整数，表示从第一列任意起点出发，到最后一列任意终点的不同路径总数。

输入输出样例 #1

输入 #1

2 2

输出 #1

4

样例解释

棋盘为 $2 \times 2$，可以从 $(1,1)$ 或 $(2,1)$ 出发，每次只能向右走一列：

• 从 $(1,1)$ 出发，可以走到 $(1,2)$ 或 $(2,2)$；
• 从 $(2,1)$ 出发，可以走到 $(1,2)$ 或 $(2,2)$。

总共有 $4$ 条不同路径。

输入输出样例 #2

输入 #2

3 3

输出 #2

17

数据范围

对于 $100\%$ 的数据，保证：

• $1 \le n,m \le 30$。

答案不超过 $64$ 位有符号整数范围。