problem684.ijs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

modn =: 1000000007

bigmodpower =: {{
	NB. perform the calculation b^e mod m
	NB. Based on this https://en.wikipedia.org/wiki/Modular_exponentiation
	'base exp mod' =. y

	result =. 1
	base =. mod|base
	while. exp > 0 do.
		if. 2|exp do.
			result =. mod|result*base
		end.
		base =. mod|*:base
		exp =. <.exp%2
	end.
	result
}}

S =: {{
	t =. <.y%9
	k =. 9|y
	pow =. bigmodpower 10;t;modn
	r =. (pow*6+k++/>:i.k)-k+6+9*t
	modn|r
}}

fib =: {{
	if. y < 2 do.
		y
	else.
		(fib y-2)+(fib y-1)
	end.
}} M.

problem684 =: modn|+/S@fib"0 x:2+i.89