(*--------------------------------------------------------------*)
(* ACM ICPC 2007-2008                                           *)
(* Northeastern European Regional Contest                       *)
(* St Petersburg - Barnaul - Tashkent - Batumi, November 28, 200*)
(*--------------------------------------------------------------*)
(* Problem H. Hanoi Towers                                      *)
(*--------------------------------------------------------------*)
(* Solution                                                     *)
(*                                                              *)
(* Author                Maxim Babenko                          *)
(*--------------------------------------------------------------*)
 
{$apptype console}
{$R+,Q+,I+,C+}

const
	IN_FILE = 'hanoi.in';
	OUT_FILE = 'hanoi.out';
	
	MAX_N = 30;

type
	long = int64;	

	TRule = record
		src, dst : integer;
	end;	
	
var
	answer : long;	
	n : integer;
	rules : array[1..6] of TRule;
	moves : array[1..MAX_N,0..2] of long;
	dst : array[1..MAX_N,0..2] of integer;
	
function DecodePeg(ch : char) : integer;
begin
	assert((ch >= 'A') and (ch <= 'C'));
	result := ord(ch) - ord('A');
end;	

procedure Init;
var
	src, i : integer;
	
begin
	for src := 0 to 2 do begin
		moves[1,src] := 1;
		for i := 1 to 6 do
			if rules[i].src = src then begin
				dst[1,src] := rules[i].dst;
				break;
			end;	
	end;
end;

procedure MakeStep(n, src : integer);
var
	res : long;
	u, v : integer;
	
begin
	res := moves[n - 1, src];  // moving top n - 1 disks from src
	u := dst[n - 1, src];      // ... to u
	v := src;                  // the largest disk still sits on v
	
	repeat
		// INVARIANT:
		// top n - 1 disks sit on u, the largest disk sits on v
		// the largest disk is about to be moved
		assert(u <> v);
		
		inc(res);                  // moving the largest disk 
		v := 3 - u - v;            // ... to the empty peg

		inc(res, moves[n - 1, u]); // moving top n - 1 disks from u
		u := dst[n - 1, u];        // ... to new u
	until u = v;	
	
	dst[n,src] := v;       
	moves[n,src] := res;
end;

procedure Solve;
var
	i, j : integer;
	
begin
	Init;
	for i := 2 to n do
		for j := 0 to 2 do
			MakeStep(i, j);
	answer := moves[n,0];	
end;
	
procedure ReadInput;
var
	i : integer;
	ch : char;
	f : array[0..2,0..2] of boolean;
	
begin
	read(n);
	assert((n >= 1) and (n <= MAX_N));
	assert(eoln);
	readln;
	fillchar(f, sizeof(f), false);
	for i := 1 to 6 do begin
		read(ch);
		rules[i].src := DecodePeg(ch);
		read(ch);
		rules[i].dst := DecodePeg(ch);
		if i < 6 then begin
			read(ch);
			assert(ch = ' ');
		end;	
		assert(not f[rules[i].src,rules[i].dst]);
		f[rules[i].src,rules[i].dst] := true;
	end;
	assert(eoln);
	readln;
	assert(eof);
end;

procedure WriteOutput;
begin
	assert(answer <= 1e18);
	writeln(answer);
end;

begin
	ReadInput;
	Solve;
	WriteOutput;
end.
