울려퍼져라

월간 향유회의 $N$명의 운영진들은 각자의 공을 가지고 게임을 하려고 한다. 각 운영진에게는 $1$부터 $N$까지의 번호가 차례대로 부여되어 있으며, $i$번 운영진은 $A\_i$개의 공을 가지고 있다.

게임은 총 $Q$개의 라운드로 진행되며, 각 라운드에는 $l\_i$번부터 $r\_i$번까지의 운영진이 참가한다. 한 라운드에 참가한 운영진들은 각자의 공을 모두 속이 보이지 않는 한 상자에 넣고 섞는다. 그리고 상자가 빌 때까지 상자에서 공을 무작위로 하나씩 뽑는데, 이때 $i$번 운영진의 공이 연속으로 뽑힐 때마다 $i$번 운영진이 $1$점을 얻는다. 각 라운드가 끝나면 해당 라운드에 참가한 운영진들은 자신의 공을 모두 회수한다.

모든 라운드가 끝난 후, 각 운영진의 점수의 기댓값을 구하여라.

첫째 줄에 운영진의 수 $N$과 라운드의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq N, Q \leq 200\\,000)$

둘째 줄에 각 운영진의 공의 수 $A\_1$, $A\_2$, $\cdots$, $A\_N$이 공백으로 구분되어 주어진다. $(1 \leq A\_i \leq 5\\,000)$

다음 $Q$개의 줄에 각 라운드에 참가할 운영진 번호의 범위 $l\_i$, $r\_i$가 공백으로 구분되어 주어진다. $(1 \leq l\_i \leq r\_i \leq N)$

$E\_1$, $E\_2$, $\cdots$, $E\_N$을 한 줄에 공백으로 구분하여 출력한다. 이때, $E\_i$는 $i$번 운영진의 점수의 기댓값이 기약분수 $\displaystyle \frac{p\_i}{q\_i}$일 때, $p\_i \equiv q\_iE\_i \pmod {10^9+7}$을 만족하는 $0$ 이상 $10^9+7$ 미만의 정수이다. 주어진 조건 내에서 $E\_i$가 항상 유일함을 증명할 수 있다.