Problem: Successful Life

时间限制：1s

空间限制：256MB

Description

​ 原力清理大师被天上掉下来的天书砸中，偶然得知了自己一生的寿命为 $n$ 年。因此，原力清理大师开始思考如何在他短暂的寿命中，演绎成功的人生。从以往的题目可以发现，原力清理大师显然是一个头脑很简单，四肢不发达（这个看不出来算了）的家伙。假设原力清理大师每一年都会给自己当年的表现打分，分数为最低 $0$ 分最高 $9$ 分的整数。原力清理大师对成功人生的定义如下：

• 饭要一口一口吃，路要一步一步走，原力清理大师不允许自己泰国丸美，因此对于任意 $i(1 \leq i \lt n)$ ，有 $a_{i+1}-a_i \leq 1$ 。
• 定义数列中的一个连续递增子序列如下：

$$对于任意 i,j(1 \leq i \lt j \leq n),若任意 k(i \leq k \lt j),有 a_k \leq a_{k+1},且当 i \neq 1 时，有 a_i \lt a_{i-1},当 j \neq n 时，有 a_j \gt a_{j+1},则称从 a_i 到 a_j 为数列 a 的一个连续递增子序列。 $$

特别的，若一个子序列中每个数字值都相等，则既不视为增区间则不视为减区间

​ 类似的，我们可以定义数列中的一个连续递减子序列。则原力清理大师希望自己的人生有始有终，即使得一个数列中的连续递增子序列和连续递减子序列数量相同。

​ 相信细心的同学们已经发现，原力清理大师早就说自己头脑简单了，所以在这等着你，希望你告诉他他能用有多少种成功的人生。（对于两个人生，只要有任意一年在两种人生中的评分不同，我们就称这两个人生为不同种类的两种人生）

Input Format

​ 输入共一行，为一个正整数 $n$ ，代表原力清理大师一生的寿命。

Output Format

​ 输出为一个正整数 $cnt$ ，代表原力清理大师在这短暂的寿命内可以拥有的成功人生的种类数。由于答案可能过大，请将答案对 $1e9+7$ 取模

Input Example #1：

3

Output Example #1：

100

Data Range

$2 \leq n \leq 120$

Explanation

​ 根据定义， $1,2,4$ 不为成功的人生，因为他同时违反了规则 $1$ 与规则 $2$ ：$4-2 \gt 1$ 且有一个递增子序列，无递减子序列。枚举可知，共有 $100$ 种。

--How many (results) did you see?

--14000605.

--How many did we win?

--1.

祝大家都能活到120岁，取得成功的人生！