RecursiveTournament

A tournament graph is a graph where every pair of distinct nodes has a single directed edge between them. Consider a touranment graph with b nodes such that the nodes are labeled with the digits of the base b. For example, if b=3, then there would be three nodes, labeled 0, 1, and 2. You are given this tournament graph in the String[] graph. graph has exactly b strings each of length b. The j-th character in the i-th string is 'Y' if there exists a directed edge from node i to node j, and 'N' otherwise. It's guaranteed that the given graph is a valid tournament graph.

You are given a int k. Consider a tournament graph in which there are b^k nodes labeled with integers from 0 to b^k-1 for a given k. To determine which way the directed edge between any two nodes x and y of this big graph points, relate it back to the input graph described above. Consider the values of x and y in base b with exactly k digits, padding the left with leading zeros if necessary. Find the leftmost digit that differs between x and y. The direction of the edge between those two digits in the input graph determines the direction of the edge between x and y in the big graph.

For example, if b=3 and k=4, then consider the nodes 1 and 6. 1 in base 3 with 4 digits is 0001, and 6 in base 3 with 4 digits is 0020. The leftmost digit in which they differ is the third digit from the left, so the edge between 1 and 6 in the big graph would have the same direction as the edge between 0 and 2 in the input graph.

An induced subgraph of a graph is a subset of its nodes along with all the edges between those nodes. A non-empty graph is strongly connected if it contains directed paths from every node to every other node. In particular, a graph with a single node is considered strongly connected. Given the input graph and number k, how many non-empty strongly connected induced subgraphs are there in the big tournament graph? Since this number can get very large, return it modulo 998244353.