SPOJ.com - Problem PIBO2

PIBO2 - Fibonacci vs Polynomial (HARD)

no tags

Define a sequence Pib(n) as following

Pib(0) = 1
Pib(1) = 1
otherwise, Pib(n) = Pib(n-1) + Pib(n-2) + P(n)

Here P is a polynomial.

Given n and P, find Pib(n) modulo 1,111,111,111.

Maybe you should solve PIBO before this task, it has lower constraints.

Input

First line of input contains two integer n and d (0 ≤ n ≤ 10⁹, 0 ≤ d ≤ 10000), d is the degree of polynomial.

The second line contains d+1 integers c₀,c₁ … c_d, represent the coefficient of the polynomial (Thus P(x) can be written as Σc_ixⁱ). 0 ≤ c_i < 1,111,111,111 and c_d ≠ 0 unless d = 0.

Output

A single integer represents the answer.

Example

Input:
10 0
0

Output:
89

Input:
10 0
1

Output:
177

Input:
100 1
1 1

Output:
343742333

Submit solution!

hide comments



	suhash: 2020-08-10 16:50:17 Looks like the time limit is a bit strict for smaller cases. My solution got TLE multiple times before getting AC [ID: 26404488] (total runtime: 2.24 sec). Here are the run times of my solution in the worst case for different values of d (n = 10^9, ci = 1111111110 for all 'i'): d = 1, time = 0.06 sec d = 10, time = 0.06 sec d = 100, time = 0.08 sec d = 1000, time = 0.10 sec d = 10000, time = 0.34 sec Consider increasing the time limit for smaller values of 'd'. Nice problem btw... :) Last edit: 2020-08-10 19:01:15
	eugenio: 2014-11-18 19:39:03 I've learnt so many things to tackle this one (even though I haven't used all of them)... Beautiful problem :) Last edit: 2014-11-18 19:40:07
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-11-13 13:25:55 Last Position! :p Any hint for opti?
	Federico LebrÃ³n: 2013-05-27 21:48:38 Hrm, this seems pretty hard. I thought with a 0.01s runtime in PIBO and O(d) memory it'd be good enough, but apparently it's not :s --ans--> You are the first who uses the special form of mod. Try to solve it without modular division or inverse. EDIT: Hah, thanks, I had done that as an "optimization", but I was working 4 times as much as I needed :p Cut the time in half now. Still, I'll try to think of a better approach - this clearly too slow! Thanks for the problem :) Last edit: 2013-05-30 03:53:40
	Francky: 2013-03-04 19:21:22 It was great to solve this hard edition, I did my best with O(d) memory print. ;-) I don't think a python solution will be possible, as it is ~ ×20 to ×100 slower on that kind of tasks. Many thanks for this PIBO2.

Submit solution!

Added by:	Michael Kharitonov
Date:	2013-02-28
Time limit:	0.100s-10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64