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