Kawazoe(@riverplus)さんのCodeIQの問題です。
問題はこちらの御世話になりました。解答例もあります。
->https://blog.goo.ne.jp/r-de-r/e/22ef7c56ea8f751e2dfb5975bc15337e
こちらにも情報があります。
->https://posfie.com/@riverplus/p/ipsiQ2P
複雑に見えますが、レベルnの図は3つのレベルn-1の図が3点でつながっていて、
其々の中の経路は独立。
レベルnの図の上から終点までの経路をf(n)通りとします。
3つのレベルn-1の図に関して、左上をA、左下をB、右下をCとしますと
Aの上からAの右下（Cの上）に行く道がf(n-1)通り、
Aの右下から終点に行く道がf(n-1)通り、
Aの上からAの左下（Bの上）に行く経路は1通り、
Bの上からBの右下に行く道がf(n-1)通り、
Bの右下（Cの左下）から終点に行く道が1通り。
よってf(n)=f(n-1)*f(n-1)+1*f(n-1)*1=f(n-1)*(f(n-1)+1)
上記では時間がかかりますので、f(2)=f(1)*(f(1)+1),f(3)=f(2)*(f(2)+1)...
というように小さいほうから計算します。
#julia ver 1.41,1.53,1.10.3
function solve(n,a)
m = 1000003
ret = 1
for k in 1 : n-1
ret = mod(ret*(ret+1),m)
end
ret = mod(ret,m)
s = a == ret ? "ok " : "no "
println(s,n,"->",ret)
end
solve(1,1)
solve(2,2)
solve(3,6)
solve(4,42)
solve(10,998593)
solve(100,682181)
solve(10000,240663)
solve(19849813,533577)
solve(99999999,454267)
solve(100000000,342482)
このままPrologに移すと時間がかかりすぎですので、剰余の周期性を利用します。
先ずレベル1<=K=Mの範囲でX=F(k) mod Mを計算して辞書（キーはX,データはK）
に登録し、同じキーが出てくるのを探します。
loop/6のK1とK番目が同じ数字で、その後k1からk-1番までの数字をくりかえします。
そこで、(n-(k1-1)) mod (k-k1)が繰り返しの中でのnの順番で、
それに繰り返しの前の(k1-1)を足したものが求める順番(レベル)です。
さらに辞書のデータ（レベル）からキーを求めます。
SWI-prologの辞書はあまり早くありませんが、簡単にデータからキーを探せます。
%SWI-Prolog ver 7.42,7.64,9.25
%:-initialization(start). %ideone,Online Prolog Compiler
%start.
loop(M,K,D,DR,X,R):-
(get_dict(X,D,K1)->(DR=D,R=[K1,K,X]);
(D1=D.put(X,K),X1 is X*(X+1) mod M,K1 is K+1,loop(M,K1,D1,DR,X1,R))).
solve(N,D,[_,K,_],R):-K>N,!,get_dict(R,D,N).
solve(N,D,[K1,K,_],R):-Y is (N-K1+1) mod (K-K1)+ K1-1 ,get_dict(R,D,Y).
start:-
M=1000003,D=dic{},loop(M,1,D,D1,1,L),f(N,A),
(solve(N,D1,L,R)->(R==A->Str=" ok ";Str=" no ");
write(fail)),write(" "),write(Str),writeln(N->R),fail.
start.
f(1,1).
f(2,2).
f(3,6).
f(4,42).
f(10,998593).
f(100,682181).
f(10000,240663).
f(19849813,533577).
f(99999999,454267).
f(100000000,342482).