L. London Underground
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a graph of the London Underground with 426 stations and 505 two-way connections between them. You are also given some subset of stations. You need to count the number of ways to add more (possibly zero) stations to this set so that no two stations are directly connected.

Two ways of adding stations are considered different if some station is present in one set and not present in another.

The number of ways could be big, so you need to output it modulo $$$998\,244\,353$$$.

Input

The first line contains one integer $$$m$$$ ($$$m = 505$$$) — the number of connections.

The following $$$m$$$ lines contain two stations each. Each station is a string of alphabetical characters, underscores, or digits.

It is guaranteed that the graph is exactly the same in all tests. It doesn't contain self-loops and duplicate edges.

The following line contains one integer $$$k$$$ ($$$0 \le k \le 426$$$) — the number of stations in the initial set. The following $$$k$$$ lines contain station names in the same format.

Output

Print the number of ways to extend the set modulo $$$998\,244\,353$$$.

Example
Input
505
Baker_Street Regents_Park
Charing_Cross Embankment
Edgware_Road__Bakerloo_ Marylebone
Embankment Waterloo
Harlesden Willesden_Junction
Harrow_and_Wealdstone Kenton
Kensal_Green Queens_Park
Kenton South_Kenton
...
2
Baker_Street
Liverpool_Street
Output
159589981
Note

You can download the complete sample input at https://pastebin.com/yuMX9tRL.

You can check the official map at https://content.tfl.gov.uk/standard-tube-map.pdf. This link is provided for reference only. It may have some differences compared to the graph in the sample.