SPOJ.com - Problem DB002

DB002 - AMUSING SEQUENCE

#math

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

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

A single line containing a natural number N.

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

Input:
5

Output:
358



	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?