题目描述

HSD 桑一直想送给 FZ 酱一个挂饰，可是总也找不到合适的。这一天，久违的雪降落在校园里，HSD 桑灵光乍现，不如收集起这些雪花做一个。
于是，HSD 桑在校园里收集了 $n$ 片雪花，准备制作雪花挂饰。可是有一个问题，他没想好做这个挂饰用多少片雪花。他因为着急制作，所以管不上那么多，直接开始。准备好雪花们，却发现没有合适的绳子把它们串起来......

好（shi）心（duo）的 HeRaNO 发现了闹心中的 HSD 桑，并且帮他找到了一些绳子，可是因为他好（shi）心（duo），他向 HSD 桑提了 $T$ 个问题。HSD 桑快烦死 HeRaNO 了，于是决定不回答。可是 HeRaNO 是绳子的提供者，如果不回答 HeRaNO 的问题，他就会收走绳子......

HeRaNO 的问题是：如果 HSD 桑每一次制作时都在一个集合里选择雪花挂饰所用的雪花数，可以做成多少种不同的雪花挂饰？我们把这个集合记为 ${ x\mid l\le x\le r\ ,\ x\in \mathbb{N} }$。因为 HSD 桑获得的绳子不是特别多，所以他想用最少的绳子将他想选择的雪花全部连接上。一根绳子只能连接两片雪花，而一片雪花上连接的绳子可以是无限多的。他能够做成的雪花挂饰数为取集合中任一元素所能做成的雪花挂饰数之和。但是 HSD 桑认为整个挂饰只有一片雪花太寒酸了，每个挂饰都做成至少有两片雪花。

因此，HSD 桑向你发出了求助，请帮助 HSD 桑解决他的问题。

一句话题意： 有 $n$ 片雪花，可以选择其中的 ${x\mid l\le x\le r,x\in \mathbb{N}}$ 片连接成一个挂饰，一个挂饰至少有两片雪花。所有选择的雪花都应被连接，且连接边数最少。求可以做成的雪花挂饰数。

输入格式

第一行三个正整数 $n$、$T$、$c$。$n$、$T$ 意义如题目描述。因为答案过大，HeRaNO 想知道这个数对 $c$ 取模后的数值；
接下来 $T$ 行，每行两个正整数 $l,r$，意义如题目描述。

输出格式

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

样例

input

4 1 1000000007
3 4

output

28

HSD 桑可以用 $4$ 片雪花中的 $3$ 片做成 $12$ 种不同的雪花挂饰，用 $4$ 片雪花中的 $4$ 片做成 $16$ 种不同的雪花挂饰； 因此用 ${ x\mid 3\le x\le 4\ ,\ x\in \mathbb{N} }$ 片雪花可做成 $12+16=28$ 种不同的雪花挂饰，对 $10^9+7$ 取模后为 $28$。

数据范围与提示

对于 $20\%$ 的数据，$n\le 10\ , \ T=1$；
对于 $40\%$ 的数据，$n\le 10^3 \ , \ T=1$；
对于 $60\%$ 的数据，$n\le 10^3 \ , \ T\le 10^3$；
对于 $100\%$ 的数据，$n\le 10^6 \ , \ T\le 10^6\ , \ 0\le l\le r\le n\ , \ c\in {10^9+7,998244353}$；

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