You are given an array a of length n$.$

It is given that the beauty$($l$,$ r$)$ is defined as the maximum integer x that appears at least x times in the subarray from I to r$($or zero if no such integer exists$).$

You are given q

queries where each query contains two integers I and r such that $1<=|<=$r$<=$n $.$ The answer to each query is the beauty$($l$,$ r$).$

You have to find the answer to the qu queries in an online way. This means that for the i$^\{$th$\}$ query, add the sum of answers over all previous queries to both I and r$,$ then do the fol

l$=$ l mod n $+1$

r$=$r mod n$+1.$

If $1>$r then swap$($l$,$ r$).$

Your task is to find the sum of answer to all q queries. Since the answer can be large, returnreturn it modulo $10^9+7$

sample input:

$5$

$5$

$3$

$2$

$5$

$1$

$3$

$2$

$34$

$34$

$55$

sample output:

$2$

Explanation:

Here, n$=5$

a$=[5,3,2,5,1]$

keervrs

a$=3,$ t$=2$ queries $=[[3,4],[3,4],[5,$

sum $=0$;

for query$1->(3,4)$

I$=3$ r$=4$

I$=($l$+$sum$)\%5+1=4$

r$=($r$+$sum$)\%5+1=5$

$1$ is the maximum integer that appears atleast $1$ times in the subarray from I to r$.$

Hence, answer for this query is $1.$

sum$=0+1$

for query$2->(3,4)$

l$=3,$r$=4$

l$=($l$+$sum$)\%5+1=5$

r$=($r$+$sum$)\%5+1=1$

swap $($l$,$r$)->=$l$=1,$r$=5$

$1$ is the maximum integer that appears atleast $1$ times in the subarray from I to$.$

Hence, answer for this query is $1.$

sum $=1+1$

query$3->(5,5)$

l$=5,$r$=5$

l$=($l$+$sum$)\%5+1=3$

r$=($r$+$sum$)\%5+1=3$

$0$ is the maximum integer that appears atleast $0$ times in the subarray from I to r$.$

Hence, answer for this query is $0.$

sum $=2+0$

so $,$our ansewer is sume $=2.$

import sysystem

def solve$($n$,$a$,$q$,$t$,$queries$)$:

#write your code here

def main$()$:

n $=$ int$($sys$.$stdin.readline$().$strip$())$

a $=[]$

for $\_$ in range$($n$)$:

a$.$append$($int$($sys$.$stdin.readline$().$strip$()))$

q $=$ int$($sys$.$stdin.readline$().$strip$())$

t $=$ int$($sys$.$stdin.readline$().$strip$())$

queries $=[]$

for $\_$ in range$($q$)$:

$|$ queries.append$($list$($map$($lambda x: int$($x$),$ sys$.$stdin.readline$().$strip$().$split$(""))))$

result $=$ get$\_$ans$($n$,$ a$,$ q$,$ t$,$ queries$)$

print$($result$)$