rt，卡了一天。如有不足欢迎在评论区补充。

• 在使用扩展欧几里得的时候，记得开 __int128，会炸longlong。（起码我是这样的）参考这里

• 取模的时候容易有负数，需要模，加，再取模。

给出我的取模代码

long long modd(long long a,long long b){
	return (a%b+b)%b;
}

应该/希望不算是讨论区题解。