#!/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);
 
   }   
 
}
 
 

IyEvdXNyL2Jpbi9wZXJsCkBNT1ZFID0gKAogIFswLDAsMV0sCiAgWzAsMSwwXSwKICBbMSwwLDBdLAogIFswLDEsMV0sCiAgWzEsMCwxXSwKICBbMSwxLDBdLAogIFsxLDEsMV0KKTsKCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCiMgMCA9IOacqum7nueHgywgMSA9IOm7nueHgywgMiA9IOeGhOa7hQoKQEZBSUxfU1RBVEUgPSAoCiAnMDAyJywnMDIwJywnMjAwJywnMDIyJywnMjAyJywnMjIwJwopOwoKCiZkZnMoMCwwLDApOwoKcHJpbnQgJGNudDsKCnN1YiBkZnN7CgogICBteSAoJGksJGosJGspID0gQF87CgogICBteSAkY3VyU3RhdGUgPSAiJGkkaiRrIjsKCiAgICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKICAgIyBmaW5hbCBzdGF0ZSAoY291bnQgYW5zd2VyKQoKICAgaWYoJGN1clN0YXRlIGVxICcyMjInKXsKICAgICAgJGNudCsrOwogICAgICByZXR1cm47CiAgIH0KCiAgICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwogICAjIGZhaWwgc3RhdGUgKHJldHVybiBpbW1lZGlhdGVseSkKCiAgIHJldHVybiBpZigkY3VyU3RhdGUgfn4gQEZBSUxfU1RBVEUpOwoKCiAgICMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCiAgICMgdHJ5IGFsbCBwb3NzaWJsZSBtb3ZlCgogICBmb3IgbXkgJG1vdmUgKEBNT1ZFKXsKCiAgICAgIG15ICR4ID0gJGkgKyAkbW92ZS0+WzBdOwogICAgICBteSAkeSA9ICRqICsgJG1vdmUtPlsxXTsKICAgICAgbXkgJHogPSAkayArICRtb3ZlLT5bMl07CgogICAgICAjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCiAgICAgICMgaW52YWxpZCBtb3ZlICh0cnkgbmV4dCkKCiAgICAgIG5leHQgaWYoIDMgfn4gWyR4LCR5LCR6XSk7CgogICAgICAjIyMjIyMjIyMjIyMjIyMjIyMKICAgICAgIyDku6XkuIvomZXnkIbnm7jlkIzni4Dms4HvvJoKICAgICAgIyAKICAgICAgIyDkvovlpoLku6XkuIvlhannqK7ni4Dms4Hoppbngrrnm7jlkIzvvJrvvJoo5pqr5pmC5b+955Wl56ys5LiJ5qC56KCf6KCLKQogICAgICAjIDEuIOign+igi++8kem7nueHg+KGkuign+igi++8keeGhOa7heaZguign+igi++8kueri+WIu+m7nueHg+KGkuign+igi++8kueGhOa7hQogICAgICAjIDIuIOign+igi++8kem7nueHg+KGkuign+igi++8keeGhOa7heKGkuS4gOacg+WFkuW+jOign+igi++8kum7nueHg+KGkuign+igi++8kueGhOa7hQoKCiAgICAgIG15ICRvbiAgPSAwOwogICAgICBteSAkb2ZmID0gMDsKCiAgICAgICRvbiA9IDEgaWYoJHggPT0gMSBhbmQgJGkgPT0gMCk7CiAgICAgICRvbiA9IDEgaWYoJHkgPT0gMSBhbmQgJGogPT0gMCk7CiAgICAgICRvbiA9IDEgaWYoJHogPT0gMSBhbmQgJGsgPT0gMCk7CgogICAgICAkb2ZmID0gMSBpZigkeCA9PSAyIGFuZCAkaSA9PSAxKTsKICAgICAgJG9mZiA9IDEgaWYoJHkgPT0gMiBhbmQgJGogPT0gMSk7CiAgICAgICRvZmYgPSAxIGlmKCR6ID09IDIgYW5kICRrID09IDEpOwoKICAgICAgbmV4dCBpZigkb24gPT0gMSBhbmQgJG9mZiA9PSAxKTsKCiAgICAgICMjIyMjIyMjIyMjIyMjIwogICAgICAjIGdvIG5leHQgc3RhdGUKICAgCiAgICAgICZkZnMoJHgsJHksJHopOwoKICAgfSAgIAoKfQoK