{"problem":{"name":"Banned Substrings","description":{"content":"You are given a set $S=\\lbrace s _ 1,s _ 2,\\ldots,s _ M\\rbrace$ of non-empty strings of length at most $6$ consisting of `a` and `b`. Find the number of strings $T$ of length $N$ consisting of `a` and","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc305_g"},"statements":[{"statement_type":"Markdown","content":"You are given a set $S=\\lbrace s _ 1,s _ 2,\\ldots,s _ M\\rbrace$ of non-empty strings of length at most $6$ consisting of `a` and `b`. Find the number of strings $T$ of length $N$ consisting of `a` and `b` that satisfy the following condition:\n\n*   $T$ does not contain $s _ i$ as a consecutive substring for any $s _ i\\in S$.\n\nSince the answer can be enormous, find it modulo $998244353$.\n\n## Constraints\n\n*   $1\\leq N\\leq10^{18}$\n*   $1\\leq M\\leq126$\n*   $N$ and $M$ are integers.\n*   $s _ i$ is a non-empty string of length at most $6$ consisting of `a` and `b`.\n*   $s _ i\\neq s _ j\\ (1\\leq i\\lt j\\leq M)$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$s _ 1$\n$s _ 2$\n$\\vdots$\n$s _ M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc305_g","tags":[],"sample_group":[["4 3\naab\nbbab\nabab","10\n\nThere are $10$ strings of length $4$ consisting of `a` and `b` that do not contain `aab`, `bbab`, or `abab` as consecutive substrings: `aaaa`, `abaa`, `abba`, `abbb`, `baaa`, `baba`, `babb`, `bbaa`, `bbba`, and `bbbb`. Thus, you should print $10$."],["20 1\naa","17711"],["1000000007 28\nbbabba\nbbbbaa\naabbab\nbbbaba\nbaaabb\nbabaab\nbbaaba\naabaaa\naaaaaa\naabbaa\nbbaaaa\nbbaabb\nbbabab\naababa\nbaaaba\nababab\nabbaba\naabaab\nababaa\nabbbba\nbaabaa\naabbbb\nabbbab\nbaaaab\nbaabbb\nababbb\nbaabba\nabaaaa","566756841\n\nPrint the answer modulo $998244353$."]],"created_at":"2026-03-03 11:01:13"}}