对于一个数 m,我们按如下方式确定一个有 (2m−2) 个点的无重边二分图 G(m):
二分图 G(m) 是一个可黑白二染色的无向图,其中有 (m−1) 个黑色点与 (m−1) 个白色点。令所有黑色点构成的集合为 X ,所有白色点构成的集合为 Y。
令 iX 表示集合 X 的编号为 i 的点,iY 表示集合 Y 的编号为 i 的点,其中满足 1≤i≤m−1 。iX 与 jY 有一条无向边,当且仅当下列条件至少有一条成立:
- i=j
- i×j≡1(modm)
令 f[G(m)] 表示 G(m) 的本质不同的最大匹配的个数。两个匹配本质不同当且仅当存在 iX 使得其在一种方案中与 jY 匹配,在另一种方案中不与 jY 匹配。
共 q 组询问,每组询问给出 l,r ,求 ∑i=lrf[G(i)]。
输出答案对 311021 取模的结果。