DB002 - AMUSING SEQUENCE

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

Added by:bhardwaj_75
Date:2015-11-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2021-12-09 18:34:58
This is not a well defined problem, There is an uncountable number of sequences whose first 6 terms are defined as above.

I think the problem setter wants the unique polynomial in IF[x] with degree 5 or below satisfying these 6 constraints (where IF=Z/nZ and n=1000000009).
2017-10-01 22:35:22
matrix exponentiation?
2017-09-10 20:56:30
IQ test, lol?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.