题目描述

给一个素数 $p$，求 $1∼n$ 关于 $p$ 的逆元。

由于输出可能很大，只需要求这些逆元的异或和即可。

输入格式

一行，两个整数 $p,n$。

输出格式

一个整数，表示 $1$ 到 $n$ 这些数关于 $p$ 的逆元的异或和。

10007 1000

14675

提示

对于所有数据，保证 $2≤p≤10^9+7,1≤n≤min(10^7,p-1)$，并且 $p$ 是素数。