|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
G - Cadenas y Patrones
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Se tiene un conjunto de $N$ patrones y se quiere determinar el número de cadenas que cumplen con exactamente $K$ de ellos. Las cadenas solo contienen caracteres del alfabeto latino en minúsculas. Un patrón es una cadena en la que aparece el carácter $\texttt{?}$ en algunas posiciones y una cadena cumple con ese patrón si tiene su misma longitud y es igual a él en todas las posiciones que no contengan un $\texttt{?}$.
Input
La primera línea de la entrada son dos enteros $N$ y $K$ ($1 \leq K \leq N \leq 15$) separados por un espacio. Las siguientes $N$ líneas contienen cada una un patron. La longitud de todos los patrones es la misma y siempre es menor o igual a $50$. Los patrones solo contienen letras minúsculas del alfabeto latino y el carácter $\texttt{?}$.
Output
La salida debe ser una sola línea con la cantidad de cadenas que cumplen con exactamente $K$ de los patrones especificados. Como este número puede ser muy grande se debe dar el resto de su división por $1,000,003$.
Sample test(s)
Input
3 1
a
b
c
Output
3
Input
2 2
a?
?b
Output
1