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}

.




#include <gmp.h>
 
int main()
{
	mpz_t a, b, m, r;
 
	mpz_init_set_str(a,	"2988348162058574136915891421498819466320"
				"163312926952423791023078876139", 0);
	mpz_init_set_str(b,	"2351399303373464486466122544523690094744"
				"975233415544072992656881240319", 0);
	mpz_init(m);
	mpz_ui_pow_ui(m, 10, 40);
 
	mpz_init(r);
	mpz_powm(r, a, b, m);
 
	gmp_printf("%Zd\n", r); /* ...16808958343740453059 */
 
	mpz_clear(a);
	mpz_clear(b);
	mpz_clear(m);
	mpz_clear(r);
 
	return 0;
}