Given an array of even size containing only 1,2,3. We can recursively take two adjacent position and remove them until size of array is 0. However we have one additional constraint, that we can not remove two adjacent if they are 1,2 or 2,1. In how many ways array can be formed(containing only 1,2,3) so that we can recursively remove adjacent position till size of array is 0.

constraints: n(size of array)<=1e5 and even

test case : for n=2 answer =7 ({1,2,3} x {1,2,3} — ((1,2) ,(2,1) ) )