Məsafələrin cəmi

У Besinin G[1], G[2], ..., G[k] ( 2 ≤ k ≤ 5 * 10^4) əlaqəli istiqamətsiz qraf kolleksiyası var. Hər bir i (1 ≤ i ≤ k) üçün G[i] dəqiq n[i] (n[i] ≥ 2) ədəd 1..n[i] ilə işarələnmiş təpələrə və m[i] (m[i] ≥ n[i] − 1) ədəd qollara malikdir. Hər bir G[i] dövrlər ehtiva edə bilər, lakin təpə cütləri arasında iki və ya daha çox qol yoxdur.

Hazırda Elza yeni istiqamətsiz qraf G yaradır, burada n[1] * n[2] * ... * n[k] təpələr var və hər biri k-li (j[1], j[2],..., j[k]) ilə işarələnmişdir, burada 1 ≤ j[i] ≤ n[i]. G-də iki təpə (j[1], j[2],...,j[k]) və (k[1], k[2],..., k[k]) qolla birləşdirilir, əgər hər bir i (1 ≤ i ≤ k) üçün j[i] və k[i] G[i]-də qolla birləşdirilibsə.

G-də eyni əlaqəli komponentdə yerləşən iki təpə arasındakı məsafəni birindən digərinə keçid üçün minimum qolların sayı kimi müəyyən edək. G-də (1, 1, ..., 1) təpəsindən eyni komponentdə olan hər bir təpəyə qədər olan məsafələrin cəmini 10^9 + 7 moduluna görə hesablayın.

Giriş məlumatları

Birinci sətir k, qraf sayını ehtiva edir.

Hər bir qrafın təsviri bir sətirdə n[i] və m[i] ilə başlayır, sonra m[i] qollar gəlir.

Ardıcıl qraflar oxunaqlılığı artırmaq üçün boş sətirlərlə ayrılır. ∑ n[i] ≤ 10^5 və ∑ m[i] ≤ 2 * 10^5 təmin edilir.

Çıxış məlumatları

G-də (1, 1, ..., 1) təpəsindən ona çatan hər bir təpəyə qədər olan məsafələrin cəmi 10^9 + 7 moduluna görə.

Nümunə 1

G 2 * 4 = 8 təpəyə malikdir, bunlardan 4-ü (1, 1) təpəsi ilə birləşdirilməyib. 1 məsafədə 2 təpə və 2 məsafədə 1 təpə var. Buna görə cavab 2 * 1 + 1 * 2 = 4.

Nümunə 2

G 4 * 6 * 7 = 168 təpəyə malikdir, hər biri (1, 1, 1) təpəsi ilə birləşdirilib. Hər bir i ∈ [1, 7] üçün i məsafədə olan təpələrin sayı aşağıdakı massivdə i-ci elementlə verilir: [4, 23, 28, 36, 40, 24, 12].