A. Synecdoche, New York
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Caden has come to understand "fate" in his own way. Leaving theater behind, he wants to use a string to represent his life through synecdoche. But in seeking a pure, original expression true to himself, he again falls into an infinite loop of self-reference. This time, Caden leaves the choice to you: portray his life for him.

Caden's synecdoche is a string $$$T$$$ of length $$$L$$$. We call $$$T$$$ valid if and only if all three conditions below hold:

  1. $$$T$$$ consists only of lowercase English letters.
  2. For every $$$i = 1, 2, \ldots, K$$$, the character of $$$T$$$ at position $$$p_i$$$ must equal the given character $$$c_i$$$, where $$$1 \le p_i \le L$$$ and $$$c_i$$$ is a lowercase letter.
  3. For every $$$i = 1, 2, \ldots, N$$$, the given string $$$s_i$$$ must not occur as a contiguous substring of $$$T$$$.

Given $$$L$$$, $$$K$$$ position constraints $$$(p_i,c_i)$$$, and $$$N$$$ forbidden substrings $$$s_i$$$, count all valid strings $$$T$$$. Output the answer modulo $$$998\,244\,353$$$.

Input

The first line contains three integers $$$L$$$, $$$K$$$, and $$$N$$$ ($$$1 \le L \le 10^{18}$$$, $$$0 \le K \le 500$$$, $$$0 \le N \le 50$$$): the string length, the number of position constraints, and the number of forbidden substrings.

Each of the next $$$K$$$ lines contains an integer $$$p_i$$$ and a lowercase letter $$$c_i$$$ ($$$1 \le p_i \le L$$$), describing a position constraint. All $$$p_i$$$ are distinct.

Each of the next $$$N$$$ lines contains a nonempty string $$$s_i$$$, describing a forbidden substring.

The sum of the lengths of all $$$s_i$$$ does not exceed $$$100$$$; that is, $$$\sum_{i=1}^N \vert{}s_i\vert{} \le 100$$$.

Output

Output one integer for each test case: the number of valid strings modulo $$$998\,244\,353$$$.

Examples
Input
3 1 1
2 b
ab
Output
650
Input
10 2 2
3 a
5 c
abc
dcabe
Output
113392371
Note

Sample 1 Explanation

The string has length $$$3$$$, its second character must be b, and it must not contain ab. Valid strings have the form ?b?; the first character can be any lowercase letter except a. There are $$$25 \times 26 = 650$$$ such strings.