순열 쿼리

$\{1, 2, \dots, N\}$의 순열 $(p(1), p(2), \dots, p(N))$이 주어진다. $(l_i, r_i)$로 이루어진 쿼리가 $Q$개 주어지므로, 각 쿼리에 대해 다음 의사 코드의 처리 결과를 출력하라.

1. $ret := 0$, $(x(1), x(2), \dots, x(N)) := (1, 2, \dots, N)$으로 둔다.
2. 각 $i \in \{1, 2, \dots, N\}$에 대해 $y(i) := p(x(i))$로 한다.
3. 각 $i \in \{1, 2, \dots, N\}$에 대해 $x(i) = y(i)$로 한다.
4. $ret := ret + x(l_i) + x(l_i+1) + \dots + x(r_i)$
5. 만약 $(x(l_i), x(l_i+1), \dots, x(r_i)) = (l_i, l_i+1, \dots, r_i)$이면 $(ret \bmod 10^9+7)$을 출력하고 종료한다. 그렇지 않으면 2번으로 돌아간다.

입력은 다음 형식으로 주어진다.

$N$ $Q$

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

$l_1$ $r_1$

$\dots$

$l_Q$ $r_Q$

각 쿼리에 대한 출력을 한 줄에 하나씩 출력하라.

• $1 \le N \le 10^5$
• $1 \le Q \le 10^4$
• $(p(1), p(2), \dots, p(N))$은 $(1, 2, \dots, N)$의 순열이다.
• 각 $i$에 대해, 어떤 $1 \le k \le 40$이 존재하여 $p^k(i) = i$이다. 여기서 $p^k(i)$는 $p(p(p(\dots p(i) \dots)))$로 $p$가 $k$번 나타나는 것이다.
• $1 \le l_i \le r_i \le N$