CodeIQ:「ディバイド・アウト」問題の解答

Kawazoe(@riverplus)さんのCodeIqの問題です。
問題とテストケースはこちらにお世話になりました。解答もあります。
->https://blog.goo.ne.jp/r-de-r/e/c0aff5fb7b5749113741d542ffecda42
こちらにも情報があります。
->https://togetter.com/li/1146993

n=d*p+rのとき
n!=1*2*..*(k*p-1)*(k*p)*(k*p+1)*..*(d*p)*..*(d*p+r)
これをpで割っていくと、k*pのpが消えていきpで割り切れなくなります。
残りの全体の積の剰余は各部分の積の剰余の積の剰余です。
(d*p+1)*..*(d*p+r)の部分の剰余は直接計算
ウイルソンの定理よりk*p+1から(k+1)*p-1の積の剰余はp-1
これがd個あるからその積の剰余は(p-1)^d mod p->dが奇数ならp-1,偶数なら1
またp*..*(k*p)*..*(d*p)をp^dで割った1*..*k*..*dからも剰余が生じますので
再帰で剰余を求めます。
まずJuliaで書きました。

#julia ver 1.41,1.53,1.73

function solve(n,p,a)
  function calc(r)
    z = 1
    for i in 1:r
        z = z * i % p
    end
    return z
  end
  function f(n,p)
    v = 0
    if n < p
        return calc(n)
    else
       (d,r) = divrem(n,p)
        sum = isodd(d) ? p-1 : 1  #k*p+1..(k+1)*p-1
        sum = sum * calc(r)   #d*p+1...d*p+r
        sum = (sum * f(d,p)) % p   #p*1,P*2...p*d
        return sum
     end
  end
  x=f(n,p)  
  s = a == x ? "ok " : "no "
  println(s,x)

end

solve(5, 3, 1)
solve(30, 11, 10)
solve(130, 13, 6)
solve(321200, 307, 124)
solve(8800, 99397, 23239)
solve(98765432170, 17, 8)
solve(916554098334, 99961, 18502)

Prologでも書きました。
fn23/3のXがd、Yがrになります。

%SWI-Prolog ver 7.42,7.64
%:-initialization(start).   %ideone
%start.

calc23(0,_,1).      %d*p+1...d*p+r
calc23(K,P,R):-K1 is K-1,calc23(K1,P,R1),R is R1*K mod P.

fn23(K,P,R):-K<P,calc23(K,P,R).
fn23(K,P,R):-
   divmod(K,P,X,Y),(1=:=X mod 2->R2=P-1;R2=1),calc23(Y,P,R3),
   R4 is R2*R3 mod P,fn23(X,P,R5),R is R4*R5 mod P.

solve23(N,P,A):-(fn23(N,P,R)->(R=:=A->Str=" ok  ";Str=" no  ");
    write(fail)),write(" "),write(Str),writeln(R),!.

start:-f23(N,P,A),solve23(N,P,A),fail.
start.

f23(5, 3, 1).
f23(30, 11, 10).
f23(130, 13, 6).
f23(321200, 307, 124).
f23(8800, 99397, 23239).
f23(98765432170, 17, 8).
f23(916554098334, 99961, 18502).