欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1190. -- 虢莔薅参加运动会

1190: 虢莔薅参加运动会

时间限制: 1 Sec  内存限制: 128 MB
提交: 2811  解决: 483
[提交][状态][讨论版]

题目描述

又到了金色的春天,一年一度的运动会就要来了,虢莔薅同学是班里的体育委员,于是他早早的就订好了运动会的时候和女朋友出去玩的计划!不对,是刷题的计划!但是今天他的导员找到了他,让他作为班级代表参加10项比赛!虢莔薅听了说:“这会死的!”,导员哈哈大笑说:“多吃点高钙片就好了”。经过了1个小时的激烈争论,两人终于达成协议,只要导员做出虢莔薅出的题虢莔薅就参加,否则就让他去刷题!于是虢莔薅说出了题:求sum(i^2)%p,1<=i<=n,p是一个素数。(sum表示求和,%表示求余)为了班级的荣誉,你快帮帮导员做出这个题吧!

输入

多组数据处理到文件结束。(不超过50组)
每行一组数据,包含两个正整数n(1<=n<=10^15),p(2<=p<=10^9)。

输出

对于每组数据,输出一个数,表示sum(i^2)%p的值

样例输入

1 7
2 11
3 13

样例输出

1
5
1

提示

来源

[提交][状态][讨论版]