Size tek olan bir sayısı veriliyor. sayıdan oluşan [a_1, a_2, \ldots, a_n] dizisi için, onun maliyetini, i<j için kenarının ağırlığının max(a_i, a_{i+1}, \ldots, a_{j-1}) olarak tanımlandığı n+1 düğümlü graftaki mükemmel eşlemenin maksimum ağırlığı olarak tanımlayalım.
Örneğin, [1, 30, 15] dizisi için, aralarındaki uzaklıkları aşağıdaki gibi olan düğümlü bir graf elde ederiz:
d(1, 2) = 1
d(1, 3) = d(1, 4) = d(2, 3) = d(2, 4) = 30
d(3, 4) = 15
Burada ((1, 2), (3, 4)) eşlemesinin ağırlığı , ((1, 3), (2, 4)) ve ((1, 4), (2, 3)) eşlemelerinin ağırlığı ise 'tır, bu yüzden tüm dizinin maliyeti 'a eşittir.
Size ikişer ikişer farklı elemanlardan oluşan uzunluğunda bir dizisi veriliyor. Bu dizinin tüm permütasyonlarının maliyetleri toplamını 10^9 + 7 moduna göre bulun.
Hatırlatalım ki, düğümlü ağırlıklı bir graftaki mükemmel eşleme, her düğümün tam olarak bir kenarın ucu olduğu kenardan oluşan bir kümedir. Mükemmel eşlemenin ağırlığı, seçilen kenarın ağırlıklarının toplamıdır.
İlk satırda bir tam sayı (1 \leq n \leq 99\,999, tektir) — dizinin uzunluğu verilir.
İkinci satırda adet ikişer ikişer farklı tam sayı b_1, b_2, \ldots, b_n (1 \leq b_i \leq 10^8) — dizinin elemanları verilir.
Bu dizinin tüm permütasyonlarının maliyetleri toplamını 10^9 + 7 moduna göre yazdırın.
Örnek 1
Örnek 2
Örnek 3
Örnekte:
[1, 30, 15] ve [15, 30, 1] dizilerinin maliyeti 'a eşittir.
[1, 15, 30], [30, 15, 1], [15, 1, 30], [30, 1, 15] dizilerinin maliyeti 'e eşittir.
Tüm permütasyonlar üzerinden toplam 60\cdot 2 + 45\cdot 4 = 300'e eşittir.