第一行是两个空格分隔的整数N和K。
之后N行每行2*K个整数A_1，B_1，A_2，B_2，...，A_K，B_K，表示N个节点的K条出边。
第i行表示第 i-1 个节点，这一行的A_S，B_S的值表示第S个大写字母对应的出边的终点为A_S，权值为B_S。
下面一行有一个字符串，表示咒语。
由于咒语的长度会非常长，将采用压缩方式给出，用[SA]表示连续S个字母A，S是一个正整数，A是单个字母。
比如说，字符串[5A]BC[3A][3C]表示的咒语为AAAAABCAAACCC。
之后一个正整数M，表示取模的底数。
字符串长度≤120000，在一个压缩节[SA]中，S≤10^9。K≤26，N≤10000，M≤10^9，所有边的权值小于10^9