String-dle Consistency Analysis

In the game of String-dle, a hidden string of k capital letters is chosen, and players guess strings of length k until they find the answer. For each guess, a grading function returns a string of feedback characters from the set \(\{O, -, x\}\) based on the following algorithm:

function grading(answer, guess):
    // answer is the hidden string, guess is the player's guess
    let count be a hash map counting letters in answer
    for i = 1 to k:
        count[answer[i]]++
    let grade be an array of length k
    // First pass marks correct positions
    for i = 1 to k:
        if answer[i] == guess[i]:
            grade[i] = 'O'
            count[guess[i]]--
    // Second pass marks letters that appear in other positions
    for i = 1 to k:
        if answer[i] != guess[i]:
            if count[guess[i]] > 0:
                grade[i] = '-'
                count[guess[i]]--
            else:
                grade[i] = 'x'
    return grade

A guess g and its corresponding grade d are said to be consistent with an answer string s if grading(s, g) = d. Given a series of guess & grade pairs, your task is to determine the number of possible answer strings that are consistent with all of the provided rounds.

Note that the grading system you are provided with might not be bug‐free. Therefore, there might be zero or more answers that satisfy the given data.

Important: All formulas and symbols must be presented in \(\LaTeX\) format. For example, the length of the answer string is denoted as \(k\), and the set of feedback characters is \(\{O, -, x\}\).

inputFormat

The input consists of multiple lines. The first line contains two integers \(n\) and \(k\) where \(n\) is the number of guess rounds and \(k\) is the length of the answer string.

This is followed by \(n\) rounds, each composed of two lines:

1. A string of \(k\) capital letters representing the guess.
2. A string of \(k\) characters where each character is one of \(O\) (capital letter O), \(-\) (dash), or \(x\) (small letter x), representing the grade.

You may assume that the input is valid and \(1 \le n, k \le 10\) (with \(k\) small enough to allow brute force solutions).

outputFormat

Output a single integer, the number of answer strings that are consistent with every guess and its grade.

sample

4 5
CRANE
xx--x
UTTER
xxOxx
NASAL
OOxOO
NATAL
OOOOO

1