DB002 - AMUSING SEQUENCE


Given a sequence of natural numbers, find its N'th term.

a1 = 3, a2 = 9, a3 = 30, a4 = 101, a5 = 358, a6 = 1443 ... aN

Input

A single line containing a natural number N.

Output

Print the N'th term of the sequence modulo 109+7.

Constraints

  • 1 ≤ N ≤ 100

Example

Input:
5

Output:
358

hide comments
o22_m_zufar_a: 2025-05-27 06:42:14

its called "riddle" for a reason :)

ramizouari: 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).

shubham9261: 2017-10-01 22:35:22

matrix exponentiation?

mahilewets: 2017-09-10 20:56:30

IQ test, lol?


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