22441번 - Perm Query 다국어

$\{1,  2,  … ,  N\}$の順列 $(p(1),  p(2),  … ,  p(n))$ が与えられる． $(l_i,  r_i)$ からなるクエリが $Q$ 個与えられるので，各クエリに対して以下の擬似コードによる処理結果を出力せよ．

1. $ret   :=   0$, $(x(1),  x(2),  … ,  x(N))  :=  (1,  2,  … ,  N)$ とおく．
2. 各$i   ∈ \{1,   2,  … ,   N\}$ について $y(i) := p(x(i))$ とする．
3. 各$i   ∈ \{1,   2,  … ,   N\}$ について $x(i)   =  y(i)$とする．
4. $ret   :=  ret + x(l_i) + x(l_i+1) + …  + x(r_i)$
5. もし $(x(l_i),  x(l_i+1),  … ,  x(r_i)) = (l_i,  l_i+1,  … ,  r_i)$ なら $(ret$ mod $10^9+7)$ を出力して終了する．そうでないなら 処理２に戻る．

入力は以下の形式で与えられる

$N$ $Q$

$p(1)$ $p(2)$ $...$ $p(N)$

$l_1$ $r_1$

$...$

$l_Q$ $r_Q$

各クエリに対する出力を1行ずつ出力せよ．

• $1 ≤ N ≤ 10^5$
• $1 ≤ Q ≤ 10^4$
• $(p(1),  p(2),  … ,  p(N))$ は $(1,  2,  … ,  N)$ の順列になっている．
• 各 $i$ に対して，ある $1 ≤ k ≤ 40$ が存在して，$p^k(i)=i$ となる．ここで，$p^k(i)$ は $p(p(p(… p(i)… )))$ で $p$ が $k$ 回現れるもの．
• $1 ≤ l_i   ≤   r_i   ≤ N$