TnT/CodeNet4Repair huggingface dataset:
Problem:
Taro's summer vacation starts tomorrow, and he has decided to make plans for it now.  The vacation consists of N days. For each i (1 \leq i \leq N), Taro will choose one of the following activities and do it on the i-th day:    * A: Swim in the sea. Gain a_i points of happiness.   * B: Catch bugs in the mountains. Gain b_i points of happiness.   * C: Do homework at home. Gain c_i points of happiness.  As Taro gets bored easily, he cannot do the same activities for two or more consecutive days.  Find the maximum possible total points of happiness that Taro gains.

Incorrect submission (verdict: Wrong Answer):
n=int(input())
m=[[]*n for i in range(3)]

for i in range(n):
    a,b,c=map(int,input().split())
    m[0].append(a)
    m[1].append(b)
    m[2].append(c)

dp=[[0]*n for i in range(3)]
dp[0][0]=m[0][0]
dp[1][0]=m[1][0]
dp[2][0]=m[2][0]

for i in range(1,n):
    for j in range(3):
        for k in range(3):
            if(j==k):continue
            dp[j][i]=max([dp[j][i],dp[k][i-1]+m[j][i-1]])

print(max([dp[0][n-1],dp[1][n-1],dp[2][n-1]]))

Fixed, accepted submission:
n=int(input())
m=[[]*n for i in range(3)]

for i in range(n):
    a,b,c=map(int,input().split())
    m[0].append(a)
    m[1].append(b)
    m[2].append(c)

dp=[[0]*n for i in range(3)]
dp[0][0]=m[0][0]
dp[1][0]=m[1][0]
dp[2][0]=m[2][0]

for i in range(1,n):
    for j in range(3):
        for k in range(3):
            if(j==k):continue
            dp[j][i]=max([dp[j][i],dp[k][i-1]+m[j][i]])

print(max([dp[0][n-1],dp[1][n-1],dp[2][n-1]]))
Problem:
Print all the integers that satisfies the following in ascending order:    * Among the integers between A and B (inclusive), it is either within the K smallest integers or within the K largest integers.

Incorrect submission (verdict: Wrong Answer):
a, b, k = map(int, input().split())
c = [d for d in range(a, b+1)]
c = set(c[0:k]+c[-k:])
c = list(c)
for e in c:
    print(e)

Fixed, accepted submission:
a, b, k =  map(int, input().split())
for i in range(a, min(a+k, b+1)):
    print(i)
for j in range(max(a+k, b-k+1), b+1):
    print(j)
Problem:
Iroha loves _Haiku_. Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.  To create a Haiku, Iroha has come up with three different phrases. These phrases have A, B and C syllables, respectively. Determine whether she can construct a Haiku by using each of the phrases once, in some order.

Incorrect submission (verdict: Wrong Answer):
A = list(map(int,input().split()))
A.sort()
if A[0] == 5 and A[1] == 5 and A[2] == 7:
  print("Yes")
else:
  print("No")

Fixed, accepted submission:
A = list(map(int,input().split()))
A.sort()
if A[0] == 5 and A[1] == 5 and A[2] == 7:
  print("YES")
else:
  print("NO")
Problem:
You are given a trapezoid. The lengths of its upper base, lower base, and height are a, b, and h, respectively.    An example of a trapezoid  Find the area of this trapezoid.

Incorrect submission (verdict: Wrong Answer):
a,b,h=[int(input())for _ in range(3)];print((a+b)*h/2)

Fixed, accepted submission:
a,b,h=map(int,open(0));print((a+b)*h//2)
Problem:
It is only six months until Christmas, and AtCoDeer the reindeer is now planning his travel to deliver gifts.   There are N houses along _TopCoDeer street_. The i-th house is located at coordinate a_i. He has decided to deliver gifts to all these houses.   Find the minimum distance to be traveled when AtCoDeer can start and end his travel at any positions.

Incorrect submission (verdict: Wrong Answer):
a = list(map(int, input().split()))
print(max(a) - min(a))

Fixed, accepted submission:
input()
a = list(map(int, input().split()))
print(max(a) - min(a))
Problem:
The word `internationalization` is sometimes abbreviated to `i18n`. This comes from the fact that there are 18 letters between the first `i` and the last `n`.  You are given a string s of length at least 3 consisting of lowercase English letters. Abbreviate s in the same way.

Incorrect submission (verdict: Wrong Answer):
l=list(input())
print(l[0]+str(len(l))+l[-1])

Fixed, accepted submission:
l=list(input())
print(l[0]+str(len(l)-2)+l[-1])
Problem:
We have a large square grid with H rows and W columns. Iroha is now standing in the top-left cell. She will repeat going right or down to the adjacent cell, until she reaches the bottom-right cell.  However, she cannot enter the cells in the intersection of the bottom A rows and the leftmost B columns. (That is, there are A×B forbidden cells.) There is no restriction on entering the other cells.  Find the number of ways she can travel to the bottom-right cell.  Since this number can be extremely large, print the number modulo 10^9+7.

Incorrect submission (verdict: Wrong Answer):
import math

def nCr(n, r):
    return (int(math.factorial(n)) // int(math.factorial(r)) // int(math.factorial(n - r))) % C

C = int(1e9) + 7
h, w, a, b = [int(x) for x in input().split()]

row = [nCr(i + h - a - 1, h - a - 1) for i in range(b, w)]
row2 = reversed([nCr(i, i - b) for i in range(b, w)])

ans = sum([x * y for x, y in zip(row, row2)])

print(ans % C)


Fixed, accepted submission:
C = int(1e9) + 7
h, w, a, b = [int(x) for x in input().split()]

fact = [1]
for x in range(1, h + w - 2):
    fact.append((x * fact[x - 1]) % C)

factinv = [1] * (h + w - 2)
factinv[h + w - 3] = pow(fact[h + w - 3], C - 2, C)
for x in reversed(range(2, h + w - 3)):
    factinv[x] = (factinv[x + 1] * (x + 1)) % C

def nCr(n, r):
    return (fact[n] * factinv[r] * factinv[n - r]) % C

ans = 0
for i in range(b, w):
    ans = (ans + nCr(i + h - a - 1, h - a - 1) * nCr(a - 1 + w - i - 1, a - 1)) % C

print(ans)
Problem:
N persons are standing in a row. The height of the i-th person from the front is A_i.  We want to have each person stand on a stool of some heights - at least zero - so that the following condition is satisfied for every person:  Condition: Nobody in front of the person is taller than the person. Here, the height of a person includes the stool.  Find the minimum total height of the stools needed to meet this goal.

Incorrect submission (verdict: Wrong Answer):
N=int(input())
A = list(map(int, input().split()))
#print(A)
count=0
count2=0
for i in range(len(A)-1):
    if A[i]>A[i+1]:
        count=A[i]-A[i+1]
        #print(count)
        A[i+1]=A[i]
    count2+=count
print(count2)

Fixed, accepted submission:
N=int(input())
A = list(map(int, input().split()))
#print(A)
count=0
count2=0

for i in range(len(A)-1):
    #print(A[i])
    if A[i]>A[i+1]:
        count=A[i]-A[i+1]
        #print(count)
        A[i+1]=A[i]
        count2+=count

print(count2)
Problem:
Snuke has a favorite restaurant.  The price of any meal served at the restaurant is 800 yen (the currency of Japan), and each time a customer orders 15 meals, the restaurant pays 200 yen back to the customer.  So far, Snuke has ordered N meals at the restaurant. Let the amount of money Snuke has paid to the restaurant be x yen, and let the amount of money the restaurant has paid back to Snuke be y yen. Find x-y.

Incorrect submission (verdict: Wrong Answer):
a = int(input())
print(800*a-15*(a//15))

Fixed, accepted submission:
N = int(input())
print(800*N-200*(N//15))
Problem:
E869120 has A 1-yen coins and infinitely many 500-yen coins.   Determine if he can pay exactly N yen using only these coins.

Incorrect submission (verdict: Wrong Answer):
N = int(input())
A = int(input())

if N % 500 < A:
    print("YES")
else:
    print("NO")



Fixed, accepted submission:
N = int(input())
A = int(input())

if N % 500 <= A:
    print("Yes")
else:
    print("No")
Problem:
You are given a trapezoid. The lengths of its upper base, lower base, and height are a, b, and h, respectively.    An example of a trapezoid  Find the area of this trapezoid.

Incorrect submission (verdict: Wrong Answer):
a = int(input())
b = int(input())
h = int(input())
print((a+b)*h/2)

Fixed, accepted submission:
a = int(input())
b = int(input())
h = int(input())
print((a+b)*h//2)
Problem:
Snuke is giving cookies to his three goats.  He has two cookie tins. One contains A cookies, and the other contains B cookies. He can thus give A cookies, B cookies or A+B cookies to his goats (he cannot open the tins).  Your task is to determine whether Snuke can give cookies to his three goats so that each of them can have the same number of cookies.

Incorrect submission (verdict: Wrong Answer):
x = input().split(" ")
a = int(x[0])
b = int(x[1])

if (a % 3 == 0 | b % 3 == 0 | (a+b) % 3 == 0 ):
    print("Possible")
else:
    print("Impossible")

Fixed, accepted submission:
x = input().split(" ")
a = int(x[0])
b = int(x[1])

if ((a % 3 == 0) or (b % 3 == 0) or ((a+b) % 3 == 0) ):
    print("Possible")
else:
    print("Impossible")
Problem:
The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.  According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.

Incorrect submission (verdict: Wrong Answer):
N, Y = map(int,input().split())
A=-1
B=-1
C=-1

for i in range(N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            if (10000*i + 5000*j + 1000*k) == Y:
                A,B,C=i,j,k
print(A,B,C)

Fixed, accepted submission:
N, Y = map(int,input().split())
A=-1
B=-1
C=-1

for i in range(N+1):
    for j in range(N+1-i):
        if (10000*i + 5000*j + 1000*(N-i-j)) == Y:
            A,B,C=i,j,(N-i-j)
print(A,B,C)
Problem:
The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.  According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.

Incorrect submission (verdict: Wrong Answer):
N, M = map(int,input().split())

for x in range(0,10):
	for y in range(0,10):
		if x + y <= N:
			z = N - (x + y)
			if x + y + z == N:
				if x * 10000 + y * 5000 + z * 1000 == M:
					print(x,y,z)
					exit()

Fixed, accepted submission:
N,Y = map(int,input().split())

list = [-1,-1,-1]

for x in range(N+1):
  for y in range(N+1-x):
    z = N - x - y
    if (x*10000) + (y*5000) + (z*1000) == Y and z <= Y:
      list[0] = x
      list[1] = y
      list[2] = z

ans = ""
for i in list:
  ans += str(i) + " "
print(ans.rstrip())
Problem:
Our world is one-dimensional, and ruled by two empires called Empire A and Empire B.  The capital of Empire A is located at coordinate X, and that of Empire B is located at coordinate Y.  One day, Empire A becomes inclined to put the cities at coordinates x_1, x_2, ..., x_N under its control, and Empire B becomes inclined to put the cities at coordinates y_1, y_2, ..., y_M under its control.  If there exists an integer Z that satisfies all of the following three conditions, they will come to an agreement, but otherwise war will break out.    * X < Z \leq Y   * x_1, x_2, ..., x_N < Z   * y_1, y_2, ..., y_M \geq Z  Determine if war will break out.

Incorrect submission (verdict: Wrong Answer):
def main():
    N , M , A , B = list(map(int,input().split()))
    X = list(map(int,input().split()))
    Y = list(map(int,input().split()))

    print(max(X))
    print(max(Y))
    flag = False
    

    for Z in range(A,B):
        if A < Z:
            if Z <= B:
                if max(X) < Z:
                    if max(Y) >= Z:
                        flag = True
                        ans = Z
    
    if flag:
        print("No War")
        print(ans)
    else:
        print("War")

if __name__ == '__main__':
    main()

Fixed, accepted submission:
def main():
    N , M , A , B = list(map(int,input().split()))
    X = list(map(int,input().split()))
    Y = list(map(int,input().split()))

    flag = False
    

    for Z in range(A,B):
        if A < Z:
            if Z <= B:
                if max(X) < Z:
                    if min(Y) >= Z:
                        flag = True
                        ans = Z
    
    if flag:
        print("No War")

    else:
        print("War")

if __name__ == '__main__':
    main()
Problem:
We will buy a product for N yen (the currency of Japan) at a shop.  If we use only 1000-yen bills to pay the price, how much change will we receive?  Assume we use the minimum number of bills required.

Incorrect submission (verdict: Wrong Answer):
n = int(input())

print(n%1000)

Fixed, accepted submission:
n = int(input())

if n%1000 == 0:
  print(0)
else:
  print(1000-n%1000)
Problem:
Find the sum of the integers between 1 and N (inclusive), whose sum of digits written in base 10 is between A and B (inclusive).

Incorrect submission (verdict: Wrong Answer):
def keta(n):
    sum = 0
    while n > 0:
        sum += n % 10
        n /= 10
    return sum

N,A,B = map(int, input().split())
total = 0
for i in range(1,N+1):
    sum = keta(i)
    if sum >= A and sum <= B:
        total += i
print(total)

Fixed, accepted submission:
def keta(n):
    sum = 0
    while n > 0:
        sum += n % 10
        n = int(n / 10)
    return sum

N,A,B = map(int, input().split())
total = 0
for i in range(1,N+1):
    sum = keta(i)
    if (sum >= A) and (sum <= B):
        total += i
print(total)
Problem:
Two children are playing tag on a number line. (In the game of tag, the child called "it" tries to catch the other child.) The child who is "it" is now at coordinate A, and he can travel the distance of V per second. The other child is now at coordinate B, and she can travel the distance of W per second.  He can catch her when his coordinate is the same as hers. Determine whether he can catch her within T seconds (including exactly T seconds later). We assume that both children move optimally.

Incorrect submission (verdict: Wrong Answer):
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if (w - v) * t >= (b - a):
  print('YES')
else:
  print('NO')

Fixed, accepted submission:
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if (a >= b):
  a, b = b, a
if (b + (w * t)) <= (a + (v * t)):
  print('YES')
else:
  print('NO')
Problem:
Quickly after finishing the tutorial of the online game _ATChat_ , you have decided to visit a particular place with N-1 players who happen to be there. These N players, including you, are numbered 1 through N, and the **friendliness** of Player i is A_i.  The N players will arrive at the place one by one in some order. To make sure nobody gets lost, you have set the following rule: players who have already arrived there should form a circle, and a player who has just arrived there should cut into the circle somewhere.  When each player, except the first one to arrive, arrives at the place, the player gets **comfort** equal to the smaller of the friendliness of the clockwise adjacent player and that of the counter-clockwise adjacent player. The first player to arrive there gets the comfort of 0.  What is the maximum total comfort the N players can get by optimally choosing the order of arrivals and the positions in the circle to cut into?

Incorrect submission (verdict: Wrong Answer):

import datetime
from decimal import Decimal, ROUND_DOWN
import heapq
from fractions import gcd
from functools import reduce
from collections import deque
# from math import factorial
import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)
# import statistics
# import numpy as np
# n = int(input())
# n, m, p = list(map(int, input().split()))
# a = list(map(int, input().split()))
#

n = int(input())
#h, w, k = list(map(int, input().split()))
#A = list(map(int, input().split()))
a = list(map(int, input().split()))


#s = list(map(int, input().split()))
# b = list(map(int, input().split()))


# print(min(15*n, 100*(n//10+1), 100*(n//10)+15*(n % 10)))

a.sort(reverse=True)
# print(a)
total = 0
for i in range(n-1):
    total += a[i]
print(total)


Fixed, accepted submission:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
total = a[0]
for i in range(n-2):
    total += a[i//2+1]
print(total)
Problem:
Write a program which calculates the cube of a given integer x.

Incorrect submission (verdict: Wrong Answer):
x=int(input());
y=x**3

Fixed, accepted submission:
x=int(input())
x=x**3
print(x)
Problem:
Write a program which reads a sequence _A_ of _n_ elements and an integer _M_ , and outputs "yes" if you can make _M_ by adding elements in _A_ , otherwise "no". You can use an element only once.  You are given the sequence _A_ and _q_ questions where each question contains _M i_.

Incorrect submission (verdict: Wrong Answer):
# ALDS1_5_A.

def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def binary_search(S, k):
    a = 0; b = len(S) - 1
    if b == 0: return S[0] == k
    while b - a > 1:
        c = (a + b) // 2
        if k <= S[c]: b = c
        else: a = c
    return S[a] == k or S[b] == k

def show(a):
    
    _str = ""
    for i in range(len(a) - 1): _str += str(a[i]) + " "
    _str += str(a[len(a) - 1])
    print(_str)

def main():
    n = int(input())
    A = intinput()
    q = int(input())
    m = intinput()
    
    nCanMake = []
    for i in range(n):
        if not A[i] in nCanMake: nCanMake.append(A[i])
        if i > 0:
            for k in range(len(nCanMake)):
                x = nCanMake[k] + A[i]
                if not x in nCanMake: nCanMake.append(x)
    nCanMake.sort()
    for i in range(q):
        if m[i] in nCanMake: print("yes")
        else: print("no")

if __name__ == "__main__":
    main()


Fixed, accepted submission:
# ALDS1_5_A.

def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def binary_search(S, k):
    a = 0; b = len(S) - 1
    if b == 0: return S[0] == k
    while b - a > 1:
        c = (a + b) // 2
        if k <= S[c]: b = c
        else: a = c
    return S[a] == k or S[b] == k

def show(a):
    
    _str = ""
    for i in range(len(a) - 1): _str += str(a[i]) + " "
    _str += str(a[len(a) - 1])
    print(_str)

def main():
    n = int(input())
    A = intinput()
    q = int(input())
    m = intinput()
    
    nCanMake = [0]
    for i in range(n):
        for k in range(len(nCanMake)):
            x = nCanMake[k] + A[i]
            if not x in nCanMake: nCanMake.append(x)
    # show(nCanMake)
    for i in range(q):
        if m[i] in nCanMake: print("yes")
        else: print("no")

if __name__ == "__main__":
    main()
Problem:
There are N people, conveniently numbered 1 through N. They were standing in a row yesterday, but now they are unsure of the order in which they were standing. However, each person remembered the following fact: the absolute difference of the number of the people who were standing to the left of that person, and the number of the people who were standing to the right of that person. According to their reports, the difference above for person i is A_i.  Based on these reports, find the number of the possible orders in which they were standing. Since it can be extremely large, print the answer modulo 10^9+7. Note that the reports may be incorrect and thus there may be no consistent order. In such a case, print 0.

Incorrect submission (verdict: Wrong Answer):
MOD=1000000007
N=int(input())
a=[int(_) for _ in input().split()]
cnt=[0]*N
if N%2==0:
    for i in range(N):
        cnt[a[i]]+=1
    f=True
    for i in range(N):
        if i%2==0 and cnt[i]!=0:
            f=False
        elif i%2==1 and cnt[i]!=2:
            f=False
    if f:
        res=1
        for i in range(N//2):
            res=(res*2)%MOD
        print(res)
    else:
        print(0)
elif N%2==1:
    for i in range(N):
        cnt[a[i]]+=1
    f=True
    for i in range(N):
        if i==0 and cnt[i]!=1:
            f=False
        elif i%2==0 and cnt[i]!=2:
            f=False
        elif i%2==1 and cnt[i]!=0:
            f=False
    if f:
        res=1
        for i in range((N-1)//2):
            res=(res*2)%MOD
        print(res)
    else:
        print(0)

Fixed, accepted submission:
MOD=1000000007
N=int(input())
a=[int(_) for _ in input().split()]
cnt=[0]*N
if N%2==0:
    for i in range(N):
        cnt[a[i]]+=1
    f=True
    for i in range(N):
        if i%2==0 and cnt[i]!=0:
            f=False
        elif i%2==1 and cnt[i]!=2:
            f=False
    if f:
        res=1
        for i in range(N//2):
            res=(res*2)%MOD
        print(res)
    else:
        print(0)
elif N%2==1:
    for i in range(N):
        cnt[a[i]]+=1
    f=True
    for i in range(N):
        if i==0 and cnt[i]!=1:
            f=False
        elif i!=0 and i%2==0 and cnt[i]!=2:
            f=False
        elif i%2==1 and cnt[i]!=0:
            f=False
    if f:
        res=1
        for i in range((N-1)//2):
            res=(res*2)%MOD
        print(res)
    else:
        print(0)
Problem:
In programming languages like C/C++, a goto statement provides an unconditional jump from the "goto" to a labeled statement. For example, a statement "goto CHECK_NUM;" is executed, control of the program jumps to CHECK_NUM. Using these constructs, you can implement, for example, loops.  Note that use of goto statement is highly discouraged, because it is difficult to trace the control flow of a program which includes goto.  Write a program which does precisely the same thing as the following program (this example is wrtten in C++). Let's try to write the program without goto statements.                 void call(int n){   int i = 1;  CHECK_NUM:   int x = i;   if ( x % 3 == 0 ){     cout << " " << i;     goto END_CHECK_NUM;   }  INCLUDE3:   if ( x % 10 == 3 ){     cout << " " << i;     goto END_CHECK_NUM;   }   x /= 10;   if ( x ) goto INCLUDE3;  END_CHECK_NUM:   if ( ++i <= n ) goto CHECK_NUM;    cout << endl; }

Incorrect submission (verdict: Wrong Answer):
a=input()
num=[]
for x in range(int(a)):
    if x!=0 and x%3==0 or x%10==3:
        num.append(x)

str_list=map(str,num)
print(" "+" ".join(str_list))

Fixed, accepted submission:
a=input()
num=[]
for x in range(int(a)+1):
    if x!=0 and x%3==0 or x%10==3 or "3" in str(x):
        num.append(x)

str_list=map(str,num)
print(" "+" ".join(str_list))
Problem:
We have a board with a 2 \times N grid. Snuke covered the board with N dominoes without overlaps. Here, a domino can cover a 1 \times 2 or 2 \times 1 square.  Then, Snuke decided to paint these dominoes using three colors: red, cyan and green. Two dominoes that are adjacent by side should be painted by different colors. Here, it is not always necessary to use all three colors.  Find the number of such ways to paint the dominoes, modulo 1000000007.  The arrangement of the dominoes is given to you as two strings S_1 and S_2 in the following manner:    * Each domino is represented by a different English letter (lowercase or uppercase).   * The j-th character in S_i represents the domino that occupies the square at the i-th row from the top and j-th column from the left.

Incorrect submission (verdict: Wrong Answer):
N = int(input())						# 5
a = list(input())


MOD = 1000000007

if N==1:
	print(3)
	exit(0)



b=[]
bSkip = False

for i in range(N-1):
	if bSkip:
		bSkip = False
		continue
	if a[i] == a[i+1]:
		b.append(2)
		bSkip = True
	else:
		b.append(1)

print(b)


if b[0]==1:
	ans = 3
else:
	ans = 6


for i in range(1, len(b)):
	if b[i-1]==1:
		ans = (ans * 2) % MOD
	else:
		if b[i]==2:
			ans = (ans * 3) % MOD


print(ans)	


Fixed, accepted submission:
N = int(input())						# 5
a = list(input())


MOD = 1000000007

if N==1:
	print(3)
	exit(0)




b=[]
bSkip = False

for i in range(N):
	if bSkip:
		bSkip = False
		continue
	if i==N-1:
		b.append(1)
	else:
		if a[i] == a[i+1]:
			b.append(2)
			bSkip = True
		else:
			b.append(1)

#print(b)


if b[0]==1:
	ans = 3
else:
	ans = 6


for i in range(1, len(b)):
	if b[i-1]==1:
		ans = (ans * 2) % MOD
	else:
		if b[i]==2:
			ans = (ans * 3) % MOD


print(ans % MOD)