-vertex tree, acyclic bidirectional connected graph painted on the wall. The vertices are conveniently labeled with. in the tree, there is a non-empty setof lowercase letters. Soon, LZR finds a note board saying that for each query. u→v and write down the chosen letters in the order of the directed chain. , and the answer to this query is the number of schemes to choose letters so that the result string. Moreover, the answers to queries may be very large, so they only need to know the answers modulo. Please help them answer the queries to enter the next level.
Gromah and LZR have entered the eighth level. There is an n_{} n -vertex tree, acyclic bidirectional connected graph painted on the wall. The vertices are conveniently labeled with 1, 2, cdots, n 1,2,⋯,n. LZR finds that for every edge e_{} e in the tree, there is a non-empty set of lowercase letters s_e s e above it. Meanwhile, Gromah finds m_{} m strings t_1, t_2, cdots, t_m t 1 ,t 2 ,⋯,t m and q_{} q queries (u_1, v_1), (u_2, v_2), cdots, (u_q, v_q) (u 1 ,v 1 ),(u 2 ,v 2 ),⋯,(u q ,v q ) beside the tree. Soon, LZR finds a note board saying that for each query (u,v)_{} (u,v) , you may choose exactly one letter from s_e s e for all edges e_{} e in the chain u rightarrow v u→v and write down the chosen letters in the order of the directed chain urightarrow v u→v to form a string str_{} str , and the answer to this query is the number of schemes to choose letters so that the result string str_{} str completely contains at least one of the m_{} m given strings t_1, t_2, cdots, t_m t 1 ,t 2 ,⋯,t m . Moreover, the answers to queries may be very large, so they only need to know the answers modulo 998244353_{} 998244353 . Please help them answer the queries to enter the next level.
