{"problem":{"name":"[USACO23FEB] Problem Setting P","description":{"content":"**Note: The memory limit for this problem is 512MB, twice the default.** Farmer John created $N(1 \\le N \\le 10^5)$ problems. He then recruited $M (1 \\le M \\le 20)$ test-solvers, each of which rated e","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9131"},"statements":[{"statement_type":"Markdown","content":"**Note: The memory limit for this problem is 512MB, twice the default.**\n\nFarmer John created $N(1 \\le N \\le 10^5)$ problems. He then recruited $M (1 \\le M \\le 20)$ test-solvers, each of which rated every problem as \"easy\" or \"hard.\"\n\nHis goal is now to create a problemset arranged in increasing order of difficulty, consisting of some subset of his $N$ problems arranged in some order. There must exist no pair of problems such that some test-solver thinks the problem later in the order is easy but the problem earlier in the order is hard.\n\nCount the number of distinct nonempty problemsets he can form, modulo $10^9+7$. \n\n## Input\n\nThe first line contains $N$ and $M$.\n\nThe next $M$ lines each contain a string of length $N$. The $i$-th character of this string is `E` if the test-solver thinks the ith problem is easy, or `H` otherwise. \n\n## Output\n\nThe number of distinct problemsets FJ can form, modulo $10^9+7$. \n\n[samples]\n\n## Note\n\n### Explanation for Sample 1\n\nThe nine possible problemsets are as follows:\n\n$[1]$  \n$[1,2]$  \n$[1,3]$  \n$[1,3,2]$  \n$[2]$  \n$[3]$  \n$[3,1]$  \n$[3,2]$  \n$[3,1,2]$  \n\nNote that the order of the problems within the problemset matters. \n\n### SCORING\n\n - Inputs $3-4$: $M=1$\n - Inputs $5-14$: $M \\le 16$\n - Inputs $15-22$: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9131","tags":["USACO","2023","快速沃尔什变换 FWT","状压 DP"],"sample_group":[["3 1\nEHE","9"],["10 6\nEHEEEHHEEH\nEHHHEEHHHE\nEHEHEHEEHH\nHEHEEEHEEE\nHHEEHEEEHE\nEHHEEEEEHE","33"]],"created_at":"2026-03-03 11:09:25"}}