A elegant ruby solution
ruby\nrequire "matrix"\n\n# @param {Integer} m\n# @param {Integer} n\n# @return {Integer}\ndef color_the_grid(m, n)\n  mod = 10**9 + 7\n  dp = m == 1 ? [[3]] : 
```ruby\nrequire "matrix"\n\n# @param {Integer} m\n# @param {Integer} n\n# @return {Integer}\ndef color_the_grid(m, n)\n  mod = 10**9 + 7\n  dp = m == 1 ? [[3]] : [[6]] * (2**(m - 2))\n  (Matrix[*$matrixs[m - 1]]**(n - 1) * Matrix[*dp]).sum % mod\nend\n\n$matrixs = [\n  [[2]],\n  [[3]],\n  [[3, 2], [2, 2]],\n  [[3, 2, 1, 2], [2, 2, 1, 2], [1, 1, 2, 1], [2, 2, 1, 2]],\n  [\n    [3, 2, 2, 1, 0, 1, 2, 2],\n    [2, 2, 2, 1, 1, 1, 1, 1],\n    [2, 2, 2, 1, 0, 1, 2, 2],\n    [1, 1, 1, 2, 1, 1, 1, 1],\n    [0, 1, 0, 1, 2, 1, 0, 1],\n    [1, 1, 1, 1, 1, 2, 1, 1],\n    [2, 1, 2, 1, 0, 1, 2, 1],\n    [2, 1, 2, 1, 1, 1, 1, 2]\n  ]\n]\n```
['Dynamic Programming', 'Ruby']