시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 1 1 1 100.000%

문제

Mirko je na nagradnoj igri osvojio zrakoplovnu kartu za put oko svijeta. Karta se sastoji od n kupona za let f1, f2, . . . , fn — k-ti kupon se može iskoristiti za jedan direktan let od grada polaska ak do grada dolaska bk. 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 fi i fj gdje je i < j onda kupon fi mora iskoristiti prije nego što iskoristi kupon fj.

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 109 + 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 ak i bk — 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 109 + 7.

예제 입력


				

예제 출력


				

힌트

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