The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n1 + F_n2, where F₁ = 1 and F₂ = 1.

It turns out that F₅₄₁, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order). And F₂₇₄₉, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that F_k is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

+-%digit_split
digit_split(N)->
	lists:map(fun(X)->X-48 end,integer_to_list(N)).

+-%pow
pow(_,0)->1;
pow(1,_)->1;
pow(A,B)->pow(A,B,1).
pow(_,0,Res)->Res;
pow(Mult,B,Res) when B band 1 == 1 ->
	pow(Mult*Mult,B bsr 1, Res*Mult);
pow(Mult,B,Res)->pow(Mult*Mult,B bsr 1, Res).

p104()->
	put(jillion,pow(10,9)),
	put(digs,lists:seq(1,9)),
	p104(2,1,1,1,1).
p104(I,ALong,BLong,AShort,BShort)->
	case lists:sort(digit_split(BShort))==get(digs) of
		true->
			FirstNine=lists:sublist(digit_split(BLong),9),
			case lists:sort(FirstNine) == get(digs) of
				true->
					io:format("~w~n",[I]);
				false->p104(I+1,BLong,ALong+BLong,BShort,(AShort+BShort) rem get(jillion))
			end;
		false->p104(I+1,BLong,ALong+BLong,BShort,(AShort+BShort) rem get(jillion))
	end.