{"problem":{"name":"[EC Final 2021] String-dle Count","description":{"content":"While most people love to play Wordle these days, Prof. Pang has become addicted to String-dle. String-dle is an interesting string-guessing game where the player tries to guess a string of $k$ capit","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9874"},"statements":[{"statement_type":"Markdown","content":"While most people love to play Wordle these days, Prof. Pang has become addicted to String-dle.\n\nString-dle is an interesting string-guessing game where the player tries to guess a string of $k$ capital letters through several rounds. In each round, the player submits a string of length $k$ as his guess, and the system grades the guess through the following pseudo-code:\n\n```\ndef grading(answer, guess):\n  let count be a hash map\n  for i = 1 to k:\n    if answer[i] not in count:\n      count[answer[i]] = 1\n    else:\n      count[answer[i]] = count[answer[i]] + 1\n  let grade be an array of length k\n  for i = 1 to k:\n    if answer[i] == guess[i]:\n      grade[i] = 'O'\n      count[guess[i]] = count[guess[i]] - 1\n  for i = 1 to k:\n    if answer[i] != guess[i]:\n      if count[guess[i]] > 0:\n        grade[i] = '-'\n        count[guess[i]] = count[guess[i]] - 1\n      else:\n        grade[i] = 'x'\n  return grade\n```\n\nThe grade consisting of $\\tt{O}$ (capital letter O), $\\tt{-}$ (dash), and $\\tt{x}$ (small letter x) is then returned to the player, and the player may base his next guess on the previous grades. The following is an example of one game Prof. Pang played:\n\n```\nG: CRANE\nA: xx--x\nG: UTTER\nA: xxOxx\nG: NASAL\nA: OOxOO\nG: NATAL\nA: OOOOO\n```\n\nStrings after $\\tt{G}$ are Prof. Pang's guesses and strings after $\\tt{A}$ are the grades of the guesses. \n\nProf. Pang really enjoys the game. He believes that he has developed a perfect strategy for it. However, today he goes mad because he thinks the grading system is bugged! He wants to have someone write an analysis program to figure out the number of possible strings that can be the answer to the puzzle based on his list of guesses and grades.\n\nSince the grading system might be bugged, it might not conform to the pseudo-code given above. So specifically, the task is to find how many strings that are consistent with the input. A string s is consistent with the input if for any guess g in the input and its corresponding grade d, grading(s, g)=d.\n\nAnd of course, you will be doing the programming.\n\n## Input\n\nThe first line consists of two integers $n$ and $k$ $(1 \\le n \\le 10^4, 1 \\le k \\le 19)$, which are the number of guesses and the length of the string, respectively.\n\nThe following lines consist of the guesses and the grades, one per line, correspondingly.\n\n## Output\n\nAn integer, denoting how many possible answers there are, modulo $10^9+7$.\n\n[samples]\n\n## Note\n\nFor the second example:\n\nIf the answer is $\\tt{ACDEF}$, the guess $\\tt{BBBAA}$ will produce a grade of $\\tt{xxx-x}$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9874","tags":["动态规划 DP","2021","O2优化","ICPC","EC Final"],"sample_group":[["2 5\nCRANE\nxx--x\nNASAL\nOOxOO","21"],["1 5\nBBBAA\nxxxx-","0"],["2 5\nABCDE\n-xxxx\nABCDE\nxxxxx","0"],["1 3\nABC\n---","2"],["1 15\nAAAAAAAAAAAAAAB\n-xxxxxxxxxxxxxx","918547951"],["1 15\nAAAAAAAAAAAAAAA\n-xxxxxxxxxxxxxx","0"],["1 1\nK\nx","25"]],"created_at":"2026-03-03 11:09:25"}}