Perm Query

You are given a permutation $(p(1), p(2), \dots, p(N))$ of $\{1, 2, \dots, N\}$. You are also given $Q$ queries of the form $(l_i, r_i)$. For each query, output the result of the following pseudocode.

1. Set $ret := 0$ and $(x(1), x(2), \dots, x(N)) := (1, 2, \dots, N)$.
2. For each $i \in \{1, 2, \dots, N\}$, set $y(i) := p(x(i))$.
3. For each $i \in \{1, 2, \dots, N\}$, set $x(i) = y(i)$.
4. $ret := ret + x(l_i) + x(l_i+1) + \dots + x(r_i)$
5. If $(x(l_i), x(l_i+1), \dots, x(r_i)) = (l_i, l_i+1, \dots, r_i)$, output $(ret \bmod 10^9+7)$ and stop. Otherwise, go back to step 2.

The input is given in the following format.

$N$ $Q$

$p(1)$ $p(2)$ $\dots$ $p(N)$

$l_1$ $r_1$

$\dots$

$l_Q$ $r_Q$

Output the answer for each query, one per line.

• $1 \le N \le 10^5$
• $1 \le Q \le 10^4$
• $(p(1), p(2), \dots, p(N))$ is a permutation of $(1, 2, \dots, N)$.
• For each $i$, there exists some $1 \le k \le 40$ such that $p^k(i) = i$. Here $p^k(i)$ is $p(p(p(\dots p(i) \dots)))$ with $p$ appearing $k$ times.
• $1 \le l_i \le r_i \le N$