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
import math
n=input()
s=math.factorial(n)+3**n-n
print (s%(10**9+7))