{"problem":{"name":"We Like AGC","description":{"content":"You are given an integer $N$. Find the number of strings of length $N$ that satisfy the following conditions, modulo $10^9+7$: *   The string does not contain characters other than `A`, `C`, `G` 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":"abc122_d"},"statements":[{"statement_type":"Markdown","content":"You are given an integer $N$. Find the number of strings of length $N$ that satisfy the following conditions, modulo $10^9+7$:\n\n*   The string does not contain characters other than `A`, `C`, `G` and `T`.\n*   The string does not contain `AGC` as a substring.\n*   The condition above cannot be violated by swapping two adjacent characters once.\n\n## Constraints\n\n*   $3 \\leq N \\leq 100$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n\n[samples]\n\n## Notes\n\nA substring of a string $T$ is a string obtained by removing zero or more characters from the beginning and the end of $T$.\nFor example, the substrings of `ATCODER` include `TCO`, `AT`, `CODER`, `ATCODER` and (the empty string), but not `AC`.","is_translate":false,"language":"English"}],"meta":{"iden":"abc122_d","tags":[],"sample_group":[["3","61\n\nThere are $4^3 = 64$ strings of length $3$ that do not contain characters other than `A`, `C`, `G` and `T`. Among them, only `AGC`, `ACG` and `GAC` violate the condition, so the answer is $64 - 3 = 61$."],["4","230"],["100","388130742\n\nBe sure to print the number of strings modulo $10^9+7$."]],"created_at":"2026-03-03 11:01:14"}}