{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e問題名 \u003c/h1\u003e\n\u003cp\u003e遺伝子は、\u003ccode\u003eA\u003c/code\u003e, \u003ccode\u003eT\u003c/code\u003e, \u003ccode\u003eG\u003c/code\u003e, \u003ccode\u003eC\u003c/code\u003e からなる文字列です。\nこの世界の遺伝子は奇妙なことに、ある構文規則に従うことが知られています。\n\u003c/p\u003e\n\u003cp\u003e構文規則は、次のような形で与えられます。\n\u003c/p\u003e\u003cpre\u003e非終端記号1: 記号1_1 記号1_2 ... 記号1_n1\n非終端記号2: 記号2_1 記号2_2 ... 記号2_n2\n...\n非終端記号m: 記号m_1 記号m_2 ... 記号m_nm\n\u003c/pre\u003e\n\u003cp\u003e記号は非終端記号または終端記号のどちらかです。\n非終端記号は小文字文字列で表され、終端記号は\u003ccode\u003eA\u003c/code\u003e, \u003ccode\u003eT\u003c/code\u003e, \u003ccode\u003eG\u003c/code\u003e, \u003ccode\u003eC\u003c/code\u003eのうちのいくつかの文字が、\"\u003ccode\u003e[\u003c/code\u003e\"と\"\u003ccode\u003e]\u003c/code\u003e\"に囲まれた文字列で表されます。\n\u003c/p\u003e\n\u003cp\u003e構文規則の例は次のようになります。\n\u003c/p\u003e\u003cpre\u003edna: a a b b\na: [AT]\nb: [GC]\n\u003c/pre\u003e\n\u003cp\u003e\"\u003ccode\u003e非終端記号i: 記号i_1 記号i_2 ... 記号i_ni\u003c/code\u003e\" を非終端記号 \u003cvar\u003ei\u003c/var\u003e のルールと呼び、ルールは、構文規則に現れる各非終端記号に対して、ちょうど 1 つづつ存在します。\n\u003c/p\u003e\n\u003cp\u003e文字列 \u003cvar\u003es\u003c/var\u003e が非終端記号 \u003cvar\u003ei\u003c/var\u003e に「\u003ccode\u003eマッチする\u003c/code\u003e」とは、 \u003cvar\u003es \u003d s\u003csub\u003e1\u003c/sub\u003e + s\u003csub\u003e2\u003c/sub\u003e + ... + s\u003csub\u003eni\u003c/sub\u003e\u003c/var\u003e となるような \u003cvar\u003es\u003c/var\u003e の部分文字列 \u003cvar\u003e{s\u003csub\u003ej\u003c/sub\u003e}\u003c/var\u003e が存在し、\u003cvar\u003es\u003csub\u003ej\u003c/sub\u003e\u003c/var\u003e (\u003cvar\u003e1 ≤ j ≤ n\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e)がルール内の記号 \u003cvar\u003ej\u003c/var\u003e にマッチすることをいいます。\n\u003c/p\u003e\n\u003cp\u003e文字列 \u003cvar\u003es\u003c/var\u003e が終端記号に「\u003ccode\u003eマッチする\u003c/code\u003e」とは、文字列が 1 文字からなり、その文字が終端記号を表す文字列に含まれることをいいます。\n\u003c/p\u003e\n\u003cp\u003e文字列が構文規則に従うとは、非終端記号 \u003cvar\u003e1\u003c/var\u003e にその文字列がマッチすることをいいます。\n\u003c/p\u003e\n\u003cp\u003eルール \u003cvar\u003ei\u003c/var\u003e は、記号のうちに、非終端記号 \u003cvar\u003ej\u003c/var\u003e (\u003cvar\u003ej ≤ i\u003c/var\u003e) を含みません。\n\u003c/p\u003e\n\u003cp\u003e構文規則と、4つの整数 \u003cvar\u003eNa\u003c/var\u003e , \u003cvar\u003eNt\u003c/var\u003e, \u003cvar\u003eNg\u003c/var\u003e, \u003cvar\u003eNc\u003c/var\u003e が与えられます。\n構文規則に従い、A をちょうど \u003cvar\u003eNa\u003c/var\u003e 個、T をちょうど \u003cvar\u003eNt\u003c/var\u003e 個、G をちょうど \u003cvar\u003eNg\u003c/var\u003e 個、C をちょうど \u003cvar\u003eNc\u003c/var\u003e 個含むような遺伝子の総数を 1,000,000,007 で割った余りを求めなさい。\n\u003c/p\u003e\n\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cblockquote\u003e\n\u003cvar\u003eNa\u003c/var\u003e \u003cvar\u003eNt\u003c/var\u003e \u003cvar\u003eNg\u003c/var\u003e \u003cvar\u003eNc\u003c/var\u003e\u003cbr\u003e\u003cvar\u003em\u003c/var\u003e\u003cbr\u003e非終端記号1: 記号 \u003cvar\u003e1\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e 記号 \u003cvar\u003e1\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e ... 記号 \u003cvar\u003e1\u003csub\u003en1\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e非終端記号2: 記号 \u003cvar\u003e2\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e 記号 \u003cvar\u003e2\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e ... 記号 \u003cvar\u003e2\u003csub\u003en2\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e...\u003cbr\u003e非終端記号 \u003cvar\u003em\u003c/var\u003e: 記号 \u003cvar\u003em\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e 記号 \u003cvar\u003em\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e ... 記号 \u003cvar\u003em\u003csub\u003enm\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\n\u003cp\u003e\u003cvar\u003e0 ≤ Na, Nt, Ng, Nc ≤ 50\u003c/var\u003e\n\u003c/p\u003e\n\u003cp\u003e\u003cvar\u003e1 ≤ m ≤ 50\u003c/var\u003e\n\u003c/p\u003e\n\u003cp\u003e\u003cvar\u003e1 ≤ ni ≤ 10\u003c/var\u003e\n\u003c/p\u003e\n\u003cp\u003e\u003cvar\u003e1 ≤ \u003c/var\u003e 記号を表す文字列の長さ \u003cvar\u003e ≤ 20\u003c/var\u003e (※記号にマッチする文字列の長さではないことに注意)\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003e総数を 1,000,000,007 で割った余り\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e1 0 1 0\n3\ndna: a b\na: [AT]\nb: [GC]\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 1\u003c/h2\u003e\n\n\u003cpre\u003e1\n\u003c/pre\u003e\n\u003cp\u003e\"AG\"の一つです。\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e1 1 1 2\n1\nk: [ATG] [ATG] [ATG] [C] [C]\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 2\u003c/h2\u003e\n\n\u003cpre\u003e6\n\u003c/pre\u003e\n\u003cp\u003e\"ATGCC\", \"AGTCC\", \"TAGCC\", \"TGACC\", \"GATCC\", \"GTACC\"の6つです。\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e3 1 1 1\n3\ninv: at b b b\nat: [ATG] b\nb: [C]\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input 3\u003c/h2\u003e\n\n\u003cpre\u003e0\n\u003c/pre\u003e\n"}}]}