Round the world ticket

Mirko won a round the world plane ticket in a prize game. The ticket consists of $n$ flight coupons $f_1, f_2, \ldots, f_n$. Coupon $k$ can be used for one direct flight from the departure city $a_k$ to the arrival city $b_k$. Unlike an ordinary round the world ticket, the arrival city on one coupon does not have to match the departure city on the next coupon. Mirko can use each coupon at most once, so he may also leave a coupon unused. The coupons may only be used in their original order: if Mirko uses coupons $f_i$ and $f_j$ with $i < j$, he must use $f_i$ before he uses $f_j$.

An itinerary is the sequence of cities visited in order on the trip, and the same city may appear in it more than once. The first and the last city of the itinerary must be Zagreb, where Mirko lives, and the itinerary must contain at least one other city. Two itineraries are the same when they list the same cities in the same order, even if Mirko used different coupons to fly them. Let $m$ be the number of different itineraries Mirko can realize with his ticket. Determine $m$ modulo $10^9 + 7$.

The first line contains a positive integer $n$ ($1 \le n \le 300000$), the number of flight coupons.

The $k$-th of the next $n$ lines contains two different strings $a_k$ and $b_k$, the codes of the departure city and the arrival city on coupon $k$. Every city code is a string of exactly three uppercase letters of the English alphabet. The code of Zagreb is ZAG.

Print the number of different itineraries modulo $10^9 + 7$.

In the first example the possible itineraries are ZAG-SPU-ZAG and ZAG-SPU-ZAG-SPU-ZAG. The first one can be flown by three different choices of two coupons, and it still counts once.