题目描述
有一个平面直角坐标系。你每次可以向上、向左或向右走，但不能经过重复的点。求出你从坐标原点出发，走 $n$ 步有多少种不同的方案。答案对 $10^9+7$ 取模。
输入
第一行一个整数 ，表示需要走的步数。
输出
仅一行，为一个整数，表示答案。
样例输入输出
提示
【样例解释1】
从 $(0,0)$ 出发走 $2$ 步，共有 $7$ 种方案：
$(0,0)\to (0,1)\to (0,2),
(0,0)\to (0,1)\to (1,1),
(0,0)\to (0,1)\to (−1,1),
(0,0)\to (1,0)\to (2,0),
(0,0)\to (1,0)\to (1,1),
(0,0)\to (−1,0)\to (−2,0),
(0,0)\to (−1,0)\to (−1,1)$
【数据范围与提示】
对于 $20\%$ 的数据，满足 $ n \leq 10$；
对于 $40\%$ 的数据，满足 $ n \leq 100$；
对于 $60\%$ 的数据，满足 $ n \leq 1000$；
对于 $80\%$ 的数据，满足 $ n \leq 10^6$；
对于 $100\%$ 的数据，满足 $ 1 \leq n \leq 10^9$ 。