Problem
Fomin'in çetesi, her biri ai kişiden oluşan n gruptan oluşur. q baskınları planlanıyor. ith raid, sayısı \([l_i, r_i]\) segmentinde bulunan her gruptan tam olarak bir haydut içerecektir. ;
Melekhov üzgün, bu yüzden her baskın için olası birimlerin sayısını modulo
\(10^9 + 7\) olarak hesaplamaya karar verdi. Ancak Gregory sürekli hayatın anlamını düşünüyor ve gerçeği arıyor, bu yüzden hesaplamalara konsantre olamıyor ve sizden yardım istiyor.
Giriş
İlk satır bir sayıdır n (\(1 <= n <= 10^5\)) – Fomin'in çetesindeki grupların sayısı.
İkinci satır n doğal sayı içerir ai (\(1 <= a_i <= 2\) ) – i-inci gruptaki
kişi sayısı.
Üçüncü satır q sayısını içerir – Baskın sayı.
Aşağıdakiler, her biri iki sayı içeren q satırlarıdır – li ve ri (\(1 <= l_i <= r_i <= n\)) – i-inci baskına
katılan grup sayısı.
Çıktı
Her biri ayrı bir satıra
q sayıları yazdırın – göreve yanıt.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
6
1 2 1 1 2 2
3
1 3
3 4
2 6
|
2
1
8 |