题目背景
小 A 找到了一张藏宝图。
他顺着藏宝图上的路线来到了一扇古老的大门前,门上有六芒星的图案。
他把手轻轻地放在六芒星上……
霎时间,六芒星光芒大放,四周亮如白昼。
(新增一组大样例)
题目描述
小 A 面前出现了 101000 扇门,每个门上都写着它自己的编号,分别为 1,2,3,…,101000。
这时,守门人小 M 向小 A 走来。
“这些门,并不普通,它有魔力。”
“我会给你一些区间 l,r,请你求出区间 [l,r] 里所有门的魔力值之和与魔力值之积。”
“因为结果可能很大,请你将结果 mod p。 ”
“如果你正确地回答了所有询问,你将会拥有这扇门后的所有宝藏。”
“哦,对了,一扇门的魔力值就是其在二进制下 1 的个数。”
简单来说,记第 i 扇门的魔力值为 di,给定的区间为 [l,r],请求出:
l∑rdimod pl∏rdimod p由于门的数量实在太多,小 A 决定向你请求帮助。
输入格式
第一行三个正整数 T,p,n(n 会在数据范围中说明)。
接下来 T 行,第 i 行两个正整数 li,ri。
输出格式
输出 T 行,每行 2 个数,由空格隔开,第 i 行分别为:
l∑rdimod pl∏rdimod p
提示
样例说明
数据 1:
3∑7di=2+1+2+2+3=10
3∏7di=2×1×2×2×3=24数据 2:
1∑10di=1+1+2+1+2+2+3+1+2+2=17
1∏10di=1×1×2×1×2×2×3×1×2×2=96
数据范围与约定

为了方便拿部分分,输入格式中的 n 为该测试点的编号。
所有具有特殊性质的测试点一共 31%。
对于 100% 的数据,有 1≤n≤27,1≤T≤10,109≤p≤1.001×109,1≤l≤r≤101000,保证 p 为质数。
对于测试点 1−20,时限 300ms,剩下的 7 个测试点时限 2s。
对于所有测试点,空间限制 256MB
“吱嘎”一声,封尘千年的大门缓缓打开。
刺眼的金光照了出来……