408049: GYM102966 M Magic Spells

Chimpa is a powerful wizard apprentice. He has been learning about magic spells lately. There are $$$m$$$ magic tuples in the world. The $$$i$$$-th magic tuple is defined as $$$(c_i, d_i, p_i)$$$, where $$$c_i$$$ and $$$d_i$$$ are lowercase letters and $$$p_i$$$ is a positive integer. A magic spell of size $$$n$$$ is a string that meets the following conditions:

• For all $$$i \in [1,n]$$$, $$$s_i$$$ is one of the first $$$20$$$ lowercase letters in the English alphabet.
• For all $$$i \in [1,n-1]$$$, there exists a magic tuple $$$(s_i, s_{i+1}, p)$$$ such that $$$i=pk+1$$$ for some non-negative integer $$$k$$$.

Recall that we denote the $$$i$$$-th character in $$$s$$$ as $$$s_i$$$.

Chimpa learned that the effect of a magic spell is unique determined by its first letter, last letter and length. There are $$$q$$$ effects that he wants to trigger. For the $$$j$$$-th effect, he wonders how many magic spells begin with the letter $$$x_j$$$, end with the letter $$$y_j$$$ and have length $$$n_j$$$. Help him to find the answer modulo $$$998244353$$$.

The first line contains two characters $$$m$$$ and $$$q$$$ ($$$1 \leq m \leq 1000$$$ and $$$1 \leq q \leq 100$$$) $$$-$$$ the number of magic tuples and the number of effects that Chimpa wants to trigger.

The following $$$m$$$ lines contain the description of the magic tuples. The $$$(1+i)$$$-th line contains two letters $$$c_i$$$ and $$$d_i$$$ followed by an integer $$$p_i$$$ ($$$c_i, d_i \in [a-t]$$$ and $$$1 \leq p_i \leq 10$$$).

The following $$$q$$$ lines contain the description of the effects. The $$$(1+m+j)$$$-th line contains two letters $$$x_j$$$ and $$$y_j$$$ followed by an integer $$$n_j$$$ ($$$x_j, y_j \in [a-t]$$$ and $$$1 \leq n_j \leq 10^{18}$$$).

For each effect, print a line containing the number of magic spells modulo $$$998244353$$$.

4 4
a a 1
a b 1
b a 1
b b 1
a a 1
a a 2
a a 10
b a 10

1
1
256
256

10 4
e m 6
t t 5
a b 2
b k 3
h a 2
b a 6
a a 1
s l 10
d e 1
o g 3
c s 3
a b 3
t t 1
e n 3

0
0
1
0