Problem
Fomin'in çetesi, her biri ai kişiden oluşan n gruptan oluşur. q baskınları planlanıyor. i-inci baskın, sayısı \([l_i, r_i]\).
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.
Girdi
İlk satır,
n sayısını içerir (
\(1 <= n <= 10^5\)) – Fomin'in çetesindeki grupların sayısı.
İkinci satırda
n doğal sayılar
ai (
\(1 <= a_i < = 10^6\)) –
i-inci gruptaki kişi sayısı.
Üçüncü satır,
q sayısını içerir – baskın sayısı.
Aşağıdakiler, her biri iki sayı içeren
q satırlarıdır –
li ve
ri (
\(1 <= l_i <= r_i <= n\)) –
i-th raid'e katılan grup sayısı.
Künye
q sayılarını her biri ayrı bir satıra yazdırın – göreve yanıt.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
6
1 3 7 1 4 100
3
1 3
34
26 |
21
7
8400 |