unittest
{
	assert( [ "2", "2 3" ].parse.expand.solve == 7 );
	assert( [ "3", "3 3 3" ].parse.expand.solve == 26 );
	assert( [ "1", "100" ].parse.expand.solve == 1 );
	assert( [ "10", "90 52 56 71 44 8 13 30 57 84" ].parse.expand.solve == 58921 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto as = input.front.split.to!( long[] );
	return tuple( as );
}

auto solve( long[] as )
{
	auto dp = new long[][]( 2, as.length );
	dp[ 0 ][ 0 ] = ( as[ 0 ] % 2 == 0 ) ? 1 : 2;
	dp[ 1 ][ 0 ] = ( as[ 0 ] % 2 == 0 ) ? 2 : 1;
	foreach( i, a; as[ 1 .. $ ] )
	{
		if( a % 2 == 0 )
		{
			// aが偶数の場合、a-1とa+1は奇数
			dp[ 0 ][ 1 + i ]  = dp[ 0 ][ i ] * 3 + dp[ 1 ][ i ];		// 偶数*偶数=偶数 or 偶数*奇数=偶数 or 奇数*偶数=偶数
			dp[ 1 ][ 1 + i ]  = dp[ 1 ][ i ] * 2;						// 奇数*奇数=奇数
		}
		else
		{
			// aが奇数の場合、a-1とa+1は偶数
			dp[ 0 ][ 1 + i ]  = dp[ 0 ][ i ] * 3 + dp[ 1 ][ i ] * 2;		// 偶数*偶数=偶数 or 偶数*奇数=偶数 or 奇数*偶数=偶数
			dp[ 1 ][ 1 + i ]  = dp[ 1 ][ i ];								// 奇数*奇数=奇数
		}
	}
	return dp[ 0 ][ $ - 1 ];
}
