题目描述
Given a sequence of natural numbers .
Find it's N'th term.
a1=3, a2=9, a3=30, a4=101, a5=358, a6=1443... ...,aN
Input
Single line containing a natural number N
Output
Print N'th term of the sequence modulo 10^9+7.
Constraints
1 <= N <=100
Example
Input:
5
Output:
358
输入格式
见题面
输出格式
见题面
样例输入
5
样例输出
358