Given an int `n`, output number of valid strings of length `n` consisting of letters `A`, `B` and `C`. Any continuous three letters containing all three letters `A`, `B`, `C` make the whole string invalid. For example, `BACCA` is not a valid string because of the first three characters, but `CCCACCAABBB` is a valid string.\n\n**Example 1:**\n```\nInput: n = 0\nOutput: 0\n```\n\n**Example 2:**\n```\nInput: n = 1\nOutput: 3\nExplanation: A, B, C\n```\n\n**Example 3:**\n```\nInput: n = 2\nOutput: 9\nExplanation: AA, AB, AC, BA, BB, BC, CA, CB, CC\n```\n\n**Example 4:**\n```\nInput: n = 3\nOutput: 21\nExplanation: 3^3 - 6 (ABC, ACB, BAC, BCA, CBA, CAB)\n```\n\n**Example 5:**\n```\nInput: n = 4\nOutput: 51\n```\n\n<details> \n  <summary>Challenge</summary>\n\nO(1) space solution.\n</details>

Given an int n, output number of valid strings of length n consisting of letters A, B and C. Any continuous three letters containing all three letters A, B, C m