#!/usr/bin/perl
@MOVE = (
  [0,0,1],
  [0,1,0],
  [1,0,0],
  [0,1,1],
  [1,0,1],
  [1,1,0],
  [1,1,1]
);

################################
# 0 = 未點燃, 1 = 點燃, 2 = 熄滅

@FAIL_STATE = (
 '002','020','200','022','202','220'
);


&dfs(0,0,0);

print $cnt;

sub dfs{

   my ($i,$j,$k) = @_;

   my $curState = "$i$j$k";

   ############################
   # final state (count answer)

   if($curState eq '222'){
      $cnt++;
      return;
   }

   #################################
   # fail state (return immediately)

   return if($curState ~~ @FAIL_STATE);


   #######################
   # try all possible move

   for my $move (@MOVE){

      my $x = $i + $move->[0];
      my $y = $j + $move->[1];
      my $z = $k + $move->[2];

      #########################
      # invalid move (try next)

      next if( 3 ~~ [$x,$y,$z]);

      ##################
      # 以下處理相同狀況：
      # 
      # 例如以下兩種狀況視為相同：：(暫時忽略第三根蠟蠋)
      # 1. 蠟蠋１點燃→蠟蠋１熄滅時蠟蠋２立刻點燃→蠟蠋２熄滅
      # 2. 蠟蠋１點燃→蠟蠋１熄滅→一會兒後蠟蠋２點燃→蠟蠋２熄滅


      my $on  = 0;
      my $off = 0;

      $on = 1 if($x == 1 and $i == 0);
      $on = 1 if($y == 1 and $j == 0);
      $on = 1 if($z == 1 and $k == 0);

      $off = 1 if($x == 2 and $i == 1);
      $off = 1 if($y == 2 and $j == 1);
      $off = 1 if($z == 2 and $k == 1);

      next if($on == 1 and $off == 1);

      ###############
      # go next state
   
      &dfs($x,$y,$z);

   }   

}