题目描述

比利时的数学家Euler在1838年找到了凸多边形划分成三角形的问题的规律。 问题的提出：在一个凸n边形中，通过n边形内部的不相交的对角线，可以把n边形拆分成若干三角形。n边形的拆分方案数记为 $h_n$ 例如五边形有如下五种拆分方案：
所以 $h_5 = 5$ 。 请你利用递推尝试找到规律，根据输入的n，输出 $h_{n+2}$，答案对 $10^9+7$ 取模。

输入格式

一个正整数n

输出格式

一个正整数 $h_{n+2}$，答案对 $10^9+7$ 取模。

3

5

约定：

$n ≤ 20$