15197번 - Letovi 다국어

Mirko je na nagradnoj igri osvojio zrakoplovnu kartu za put oko svijeta. Karta se sastoji od n kupona za let f₁, f₂, . . . , f_n — k-ti kupon se može iskoristiti za jedan direktan let od grada polaska a_k do grada dolaska b_k. Za razliku od uobičajnih karata za put oko svijeta, grad dolaska na jednom kuponu ne mora nužno odgovarati gradu polaska na sljedećem kuponu. Svaki kupon za let Mirko može iskoristiti najviše jednom (dakle dozvoljeno je da ga uopće ne iskoristi). Medutim, kuponi se samo smiju koristiti originalnim redoslijedom — ako Mirko iskoristi kupone f_i i f_j gdje je i < j onda kupon f_i mora iskoristiti prije nego što iskoristi kupon f_j.

Itinerar je niz gradova redom posjećenih na putu oko svijeta, a u kojem se isti grad može pojavljivati i više od jednom. Prvi i posljednji grad u itineraru mora biti Zagreb gdje Mirko živi, a itinerar mora sadržavati barem još jedan drugi grad. Neka je m broj različitih takvih itinerara koje Mirko može ostvariti sa svojom kartom. Odredite koliko je m modulo 10⁹ + 7.

U prvom redu se nalazi prirodni broj n (1 ≤ n ≤ 300 000) — broj kupona za let. U k-om od sljedećih n redova se nalaze dva različita niza znakova a_k i b_k — kodovi grada polaska i grada dolaska na k-tom kuponu. Svaki kod grada je niz od točno tri velika slova engleske abecede. Kod grada Zagreba je ZAG.

Ispišite traženi broj itinerara modulo 10⁹ + 7.

U prvom primjeru test podataka, mogući itinerari su ZAG-SPU-ZAGi ZAG-SPU-ZAG-SPU-ZAG.