Find the last   40   decimal digits of   




a

b




{\displaystyle a^{b}}

,   where

   



a
=
2988348162058574136915891421498819466320163312926952423791023078876139


{\displaystyle a=2988348162058574136915891421498819466320163312926952423791023078876139}


   



b
=
2351399303373464486466122544523690094744975233415544072992656881240319


{\displaystyle b=2351399303373464486466122544523690094744975233415544072992656881240319}




A computer is too slow to find the entire value of   




a

b




{\displaystyle a^{b}}

.

Instead, the program must use a fast algorithm for modular exponentiation:   




a

b



mod


m


{\displaystyle a^{b}\mod m}

.

The algorithm must work for any integers   



a
,
b
,
m


{\displaystyle a,b,m}

,     where   



b
≥
0


{\displaystyle b\geq 0}

   and   



m
>
0


{\displaystyle m>0}

.




 
We will call the lib_BN library for big numbers: 
 
{require lib_BN}
 
In this library {BN.compare a b} returns 1 if a > b, 0 if a = b and -1 if a < b. 
For a better readability we define three small functions
 
{def BN.= {lambda {:a :b} {= {BN.compare :a :b} 0}}} 
-> BN.=
{def BN.even? {lambda {:n} {= {BN.compare {BN.% :n 2} 0} 0}}} 
-> BN.even?
{def BN.square {lambda {:n} {BN.* :n :n}}} 
-> BN.square
 
{def mod-exp
 {lambda {:a :n :mod}
  {if {BN.= :n 0}
   then 1
   else {if {BN.even? :n}
   then {BN.% {BN.square {mod-exp :a {BN./ :n 2} :mod}} :mod}
   else {BN.% {BN.* :a   {mod-exp :a {BN.- :n 1} :mod}} :mod}}}}}
-> mod-exp
 
{mod-exp 
  2988348162058574136915891421498819466320163312926952423791023078876139 
  2351399303373464486466122544523690094744975233415544072992656881240319 
  {BN.pow 10 40}}
-> 1527229998585248450016808958343740453059   // 3300ms
 