Segment Tree

题号：NC305997
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

广义线段树是说，相比于普通的线段树，其中的结点的左右儿子所对应的区间的是任意的，不一定各占该结点区间的一半。

举例来说，一棵以区间 $[1,5]$ 为根的广义线段树，其结构可能如下：根的左儿子是 $[1,1]$ ，是一个叶子结点，而右儿子则是 $[2,5]$ ；结点 $[2,5]$ 则拥有两个儿子 $[2,3]$ 与 $[4,5]$ ，而这两个儿子又各自有两个叶子结点作为它们的左右儿子。

现有一棵在区间 $[1,n]$ 上随机生成的广义线段树，其生成方式如下：

从区间 $[1,n]$ 开始：

假设当前线段树结点对应的区间是 $[l,r]$ 则：
若 $l<r$ ，那么在 $l,l+1,\dots,r-1$ 中均匀随机地选一个数 $k$ ，则该结点的左儿子所对应的区间是 $[l,k]$ ，右儿子是 $[k+1,r]$ ，接着，递归地为其左儿子与右儿子建立子树；

若 $l=r$ ，那么该结点是整棵广义线段树的叶子结点，直接结束。

另外，与普通的线段树类似，我们定义在广义线段树上查询某一个区间 $[ql,qr]$ 的过程：

从根结点 $[1,n]$ 开始：

假设当前线段树结点对应的区间是 $[l,r]$ ，则：
若 $[l,r]$ 被 $[ql,qr]$ 包含，则返回，无需访问其子结点；
否则，若该结点的左儿子与 $[ql,qr]$ 有交，则递归地访问其左儿子；同样的，若该结点的右儿子与 $[ql,qr]$ 有交，则也会递归地访问其右儿子。

举例来说，不管该广义线段树的结构如何，在其上查询 $[1,n]$ ，则一定只会访问根结点，访问的结点数量为 $1$ ；如果在其上查询 $[2,2]$ ，则一定会从根结点一路访问到 $[2,2]$ 对应的叶子结点，那么访问的结点数量就为 $[2,2]$ 所对应的叶子结点到根结点这条路径上的点数（对于前述题面里给出的那棵以 $[1,5]$ 为根的广义线段树，查询 $[2,2]$ 访问的结点数量就是 $4$ ，即 $[1,5],[2,5],[2,3],[2,2]$ ）。

现在有 $q$ 个询问，每个询问给出一个查询区间 $[ql,qr]$ 。我们希望知道，如果在这棵随机生成的广义线段树上查询 $[ql,qr]$ ，那么期望会访问多少个广义线段树结点。

输入描述:

第一行一个整数 ，表示线段树对应区间的长度。

接下来一行一个整数 ，表示将要询问的区间数。

接下来  行，每行两个整数 ，表示每次询问的区间。

输出描述:

输出  行，第  行一个整数 ，表示第  个询问对应的期望访问次数，答案对  取模。

可以证明答案为有理数 ，你需要输出  使得 。可以证明这样的  一定存在。

示例1

输入

复制

输出

复制

备注:

。