#1481. 费马大定理

费马大定理

题目描述

给出质数 pp,求有多少个正整数 knk\le n 满足存在 0<x,y,z<p0<x,y,z<p 使 xk+ykzk(modp)x^k+y^k\equiv z^k\pmod p

输入格式

一行两个正整数 p,np,n

输出格式

一行一个正整数,为答案。

样例 1

3 10
5
692707 470472961806427201
470453944730018769

数据范围与提示

对于 100%100\% 的数据,2p1062\le p\le 10^61n10181\le n\le 10^{18}