title: How to calculate the different combinations of an NxM grid with 3-valid values
body: <p>I have 3 valid values: a,b,c
  I can insert them in a Nx3 grid in such a way that no row or column contains cells that are the same values. How can I calculate the number of valid patterns that can be created using N rows?</p>
  <p>For example, if N = 4, the total number of valid pattern is 296490.
  <a href="https://i.stack.imgur.com/t1fBZ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/t1fBZ.png" alt="enter image description here" /></a></p>
  <p>This is my attempt:</p>
  <pre><code>def countPatterns(n):
  
      dp1, dp2 = 6,6
      mod = 10 ** 9 + 7
      
      for i in range(2, n+1):
          dp1, dp2 = (dp1 * 3 + dp2 * 2) % mod, (dp1 * 2 + dp2 * 2) % mod
      return (dp1 + dp2) % mod
  </code></pre>
  <p>When N = 4, the output should be 174 but I'm getting 54.</p>