세계 일주 항공권

미르코가 경품 행사에서 세계 일주 항공권을 받았다. 이 항공권은 $n$장의 탑승 쿠폰 $f_1, f_2, \ldots, f_n$으로 이루어져 있고, $k$번째 쿠폰으로는 출발 도시 $a_k$에서 도착 도시 $b_k$로 가는 직항 한 편을 탈 수 있다. 흔한 세계 일주 항공권과 달리, 한 쿠폰의 도착 도시가 다음 쿠폰의 출발 도시와 같을 필요는 없다. 미르코는 각 쿠폰을 최대 한 번만 쓸 수 있고, 아예 쓰지 않아도 된다. 다만 쿠폰은 원래 순서대로만 쓸 수 있다. 즉 $i < j$인 쿠폰 $f_i$와 $f_j$를 모두 쓴다면 $f_i$를 $f_j$보다 먼저 써야 한다.

여정은 여행에서 방문한 도시를 순서대로 나열한 수열이고, 같은 도시가 여러 번 나올 수도 있다. 여정의 첫 도시와 마지막 도시는 미르코가 사는 자그레브여야 하며, 여정에는 다른 도시가 적어도 하나 더 있어야 한다. 도시가 같은 순서로 나열되면 미르코가 서로 다른 쿠폰을 써서 날아갔더라도 같은 여정이다. 미르코가 이 항공권으로 만들 수 있는 서로 다른 여정의 수를 $m$이라고 하자. $m$을 $10^9 + 7$으로 나눈 나머지를 구하시오.

첫 줄에 탑승 쿠폰의 수를 나타내는 자연수 $n$ ($1 \le n \le 300000$)이 주어진다.

이어지는 $n$개 줄 중 $k$번째 줄에는 $k$번째 쿠폰의 출발 도시 코드 $a_k$와 도착 도시 코드 $b_k$가 주어지고, 두 코드는 서로 다르다. 모든 도시 코드는 알파벳 대문자 정확히 세 개로 이루어진 문자열이다. 자그레브의 코드는 ZAG이다.

서로 다른 여정의 수를 $10^9 + 7$으로 나눈 나머지를 출력한다.

첫 번째 예제에서 가능한 여정은 ZAG-SPU-ZAG과 ZAG-SPU-ZAG-SPU-ZAG 두 가지다. 앞의 여정은 쿠폰 두 장을 고르는 서로 다른 방법 세 가지로 만들 수 있지만 한 번만 센다.