题目背景

LHJ老师让刘队整理一下饱和烷烃的同分异构数，但是刘队认为这太简单了，于是他将这个任务交给了你

题目描述

现在已知碳原子个数 \(n\)，求对应的烷基有多少种同分异构体。

输入输出格式

输入格式

输入一行，一个整数 \(n\)，表示烷基中碳原子的数目。

输出格式

输出该烷基同分异构体的数目，对 \(10^9 + 7\) 取模。

样例

输入

6

输出

17

数据范围

\( 1\le n\le 400\)