울려퍼져라

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

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

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

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

둘째 줄에 각 운영진의 공의 수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq 5000$)

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

$E_1, E_2, \cdots, E_N$을 한 줄에 공백으로 구분하여 출력한다. 이때 $E_i$는 $i$번 운영진의 점수의 기댓값이 기약분수 $\frac{p_i}{q_i}$일 때, $p_i \equiv q_i E_i \pmod{10^9+7}$을 만족하는 0 이상 $10^9+7$ 미만의 정수이다. 주어진 조건에서 $E_i$가 항상 하나로 정해짐을 증명할 수 있다.