Description

HSD桑一直想送给FZ酱一个挂饰，可是总也找不到合适的。这一天，久违的雪降落在校园里，HSD桑灵光乍现，不如收集起这些雪花做一个。
于是，HSD桑在校园收集了$n$片雪花，准备制作雪花挂饰。可是有一个问题，因为HSD桑的思路是流动的，他没想好这个挂饰有多少片雪花。
可是他因为着急制作，所以不管那么多了，直接开始。准备好雪花们，却发现没有合适的绳子把它们穿起来......
好（shi）心（duo）的HeRaNO发现了闹心ing的HSD桑，于是帮他找到了一些绳子，可是因为他好（shi）心（duo），他向HSD桑提了$T$个问题，询问HSD桑利用这些雪花可以做成多少种不同的雪花挂饰。
HSD桑快烦死HeRaNO了，于是决定不回答。可是HeRaNO是绳子的提供者，如果不回答HeRaNO的问题，HeRaNO就会收走绳子......
因为HSD桑的思路是流动的，他每一次制作时都会在一个区间里选择雪花挂饰用的雪花数，我们把区间记为$[l,r]$，为闭区间。因为HSD桑获得的绳子不是特别多，绳子用多了也麻烦，于是他想用最少的绳子将他想选择的雪花连接上。
因此，HSD桑向你发出了求助，请帮助HSD桑解决他的问题。

Format

Input

第一行为三个正整数$n$，$T$，$R$。$n$，$T$意义如题。请在$R$的剩余系下完成计算；
第$2$~$T+1$行，每行两个整数$l$，$r$，意义如题。

Output

输出$T$行，对于第$i$行表示对于第$i$个问题的答案。

Sample

Input

4 1 1000000007
3 4

Output

28

Explanation

HSD桑可以用$4$片雪花中的$3$片做成$12$种不同的雪花挂饰，可以用$4$片雪花中的$4$片做成$16$种不同的雪花挂饰；
因此用$[3,4]$片雪花可做成$12+16=28$种不同的雪花挂饰。

Limitation

共$20$组测试数据，每组测试数据时间限制为2s，内存限制为512MiB。
其中：
$50\%$的数据：$R=10^9+7$；
其余$50\%$的数据：$R=998244353$。
$10\%$的数据：$n\le 10$；
$50\%$的数据：$n\le 10^6$，$T=1$；
对于这$50\%$的数据，有$50\%$的数据$l=r$；
$100\%$的数据：$n\le 10^6$，$T\le 10^6$，$0\le l\le r\le n$。

Hint

我们都知道，世界上几乎没有完全相同的两片雪花，所以本题中每片雪花可看做两两不同。
两种方案相同，当且仅当所选雪花完全相同且每一片雪花连接的雪花也完全相同。

Source

Problem by HeRaNO