{"raw_statement":[{"iden":"problem statement","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."},{"iden":"notes","content":"A 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`."},{"iden":"constraints","content":"*   $3 \\leq N \\leq 100$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$"},{"iden":"sample input 1","content":"3"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"4"},{"iden":"sample output 2","content":"230"},{"iden":"sample input 3","content":"100"},{"iden":"sample output 3","content":"388130742\n\nBe sure to print the number of strings modulo $10^9+7$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}