갱스 오브 포민
Problem
<사업부>
포민의 갱단은 n개의 그룹으로 구성되어 있으며 각 그룹에는 i명이 있습니다. q 습격이 예정되어 있습니다. i번째 습격은 세그먼트 \([l_i, r_i]\)에 번호가 있는 각 그룹에서 정확히 한 명의 도적을 갖게 됩니다. ;
Melekhov는 슬프기 때문에 각 습격에 대해
\(10^9 + 7\) 모듈로 가능한 단위 수를 계산하기로 결정했습니다. 하지만 그레고리는 삶의 의미에 대해 끊임없이 고민하고 진리를 찾고 있기 때문에 계산에 집중하지 못하고 당신에게 도움을 요청합니다.
<사업부>
입력
첫 번째 줄은 숫자 n입니다(\(1 <= n <= 10^5\)) – 포민 갱단의 그룹 수
두 번째 줄에는 n개의 자연수 ai가 포함됩니다(\(1 <= a_i <= 2\) ) – i-번째 그룹의 사람 수.
세 번째 줄에는 숫자 q가 포함됩니다. 습격 횟수.
다음은 각각 두 개의 숫자를 포함하는 q 줄입니다. li 및 ri (\(1 <= l_i <= r_i <= n\)) – i-번째 습격
에 참여하는 그룹 수
<사업부>
출력