{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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)$"},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"4 3\naab\nbbab\nabab"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"20 1\naa"},{"iden":"sample output 2","content":"17711"},{"iden":"sample input 3","content":"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"},{"iden":"sample output 3","content":"566756841\n\nPrint the answer modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}