逆元1

题目描述

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

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

输入格式

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

输出格式

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

样例输入

10007 1000

样例输出

14675

数据范围

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