Problem:


Score: 500 points

Problem Statement

N people are standing in a queue, numbered 1, 2, 3, ..., N from front to back. Each person wears a hat, which is red, blue, or green.

The person numbered i says:

"In front of me, exactly A_i people are wearing hats with the same color as mine."

Assuming that all these statements are correct, find the number of possible combinations of colors of the N people's hats.

Since the count can be enormous, compute it modulo 1000000007.

Constraints

1 \leq N \leq 100000

0 \leq A_i \leq N-1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 A_3 ... A_N

Output

Print the number of possible combinations of colors of the N people's hats, modulo 1000000007.

Sample Input 1

6
0 1 2 3 4 5

Sample Output 1

3

We have three possible combinations, as follows:

Red, Red, Red, Red, Red, Red

Blue, Blue, Blue, Blue, Blue, Blue

Green, Green, Green, Green, Green, Green

Sample Input 2

3
0 0 0

Sample Output 2

6

Sample Input 3

54
0 0 1 0 1 2 1 2 3 2 3 3 4 4 5 4 6 5 7 8 5 6 6 7 7 8 8 9 9 10 10 11 9 12 10 13 14 11 11 12 12 13 13 14 14 15 15 15 16 16 16 17 17 17

Sample Output 3

115295190



Sample input:
6
0 1 2 3 4 5


Sample output:
3

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

mod = 1000000007
fmax =-1
smax =-1
tmax =-1
for i in a:
    if fmax < i:
        fmax = i
    elif smax < i:
        smax = i
    elif tmax < i:
        tmax = i

a = a[::-1]
result = 1
if fmax != smax and smax != tmax:
    result = 6
if fmax != smax and smax == tmax:
    result = 3
if fmax == smax and smax != tmax:
    result = 3
for i in a:
    if i == fmax and i == smax and i == tmax:
        result = result * 3 % mod
        fmax -= 1
    elif i == fmax and i == smax and i != tmax:
        result = result * 2 % mod
        fmax -= 1
    elif i == fmax and i != smax and i == tmax:
        result = result * 2 % mod
        fmax -= 1
    elif i != fmax and i == smax and i == tmax:
        result = result * 2 % mod
        smax -= 1
    elif i == fmax and i != smax and i != tmax:
        fmax -= 1
    elif i != fmax and i == smax and i != tmax:
        smax -= 1
    elif i != fmax and i != smax and i == tmax:
        tmax -= 1
print(result)

Submission status: Wrong Answer

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAOi9410C/+1de3wTVb6fJG0Jrya8pCJCwQpUltJAgdYXLSUwgRS6tCCrwlDSlFbTpJ9kAsX1AbZVY6yyXq/r3bsPrnuv6+69dxf3ri6yLlAQ6uKKCIqIivgAJxQUX1gfkPv7nXMmPTOZqeB6718GmpPfd37n8Tu/3/mdx8ycc4fbO8dqsQjqxypcKyD1xCWlhC5l+D2+FAtgxUJf+B4tjBSygM7k+EqFUk3YzZJWQzvjs8FfBvwVWyldbC3VhCMZnxpauDBT4D+lmvC5JYImFITcVDws66FlFD20bIUmdGZQvLCPNp6Vxetm8boZvxoKVkETqvJlsL9qhlczudRwNuObzfHjp/KYXIu/D1WyclaWasJWxteqi/dDiJclnP/HycJFan4m9TKBlV8NVT1MDjSsnF40OVA7KdAQjDZPai6ePml6UUEkVDCFlMnJeOcuWKypxxxW5qHMBvD6fe/+tXu38McJv//qxKPDnhn9wb+eqT+L10pYPFRJW9BZnzGmr9UiFAnrIGm8djX8lcHfH9+Y+kq/9RukX/j+uuv+xuRz97T5Lnq5amPLfT8q/WjSR9Ly7NzVhRPcr3i3nxi3fegjA8p/ObJp81rPzU/1Vj/vQQEGG+AHrMb4ZIsx/kfBGHemLEz7GW2Cv5hpnM5tJvjzJvm2m/CLWcZ4HxP8OhP87gxjvMEk33Em6RSb1POTJvjFJulMNanPVSbpNJik87EJ/2gT/oUm+f6TiV4yTeyn2iTfLSb8A03Ks8KEf6EJ/xkT+x9jks5jJnp/2gTfYpL+7Sb102BSn1NNyr/WpN6GmvD/3kSuRpNylpmkc9Kk/CUm6RwxqR/ZBN9jUs4PTNrXeJN62G+S/l6Tcl5pIu9fTfK9DNIZI4wQNq2k/UgOwwcz/LRvhaYfGp9JcaGW4ksZ3j+D4SyddQz/D5bvhotLNfnOZfWzYoQWnw/5DoJ0jrL0VVu6JYPign+Fpn97zULzXbdSy+9g9Vmoy7cyk6azcaU2nWtY+kcZ7mQX5jK5VtTq5GL1f1pXfgH624hc65s4EfvY6YIkrWoMBaWIXBOWJUmQ5q2WFvlXNURkf7g8UBOJ+COC5KmukGr9YQZXV5QHQkF/dc3KgJ9eM74iNcn1YX9NrXSzf63kg18ygr7mGqku7PdL/mafv0luCAUF6foFVZEiyLbJVShhThE5HFrrXjS/qsbjc5PLoRK40BCM+MOyJ+B2L6oKVUt4YX6VPM0nr23yA6NrKvCsaaj1B4GzQXavBoYq2TVDkqAcoTXSSihKTSAQ8q2mMSOuqXUNwVqpriEckaVQnbtyvq+xkWY3rS4QjdSrSUznk/DVRGSSAlyYGo4G5YZGECYcDoVnu7gIIRDCX9OoFtoHqMtXXxOW5HBNgxyB8oIUkMLKmkiDT+X2VEvVhZK7arpUOb9qqhRg9UUyJymXQC03NgShKmkRIuUurKcIKXd1NSRY0pNgQ3AVS9Ygd1K3tHLl4oZQBGSL+Is8UHFMDMCnQ2XVBPw9gE5glnmqJFCBvNIQatQgMisd5GdYI9N8AX9N2A1XpkgeKBP8ycRsQPQphaoWQlFUlxSuCa7yQ5aqNqcTbYLNylIwpFUoXp7BKVt3vdoDJePtEQGdrEwVK8HUg2ADsq+es1soW5Xkb2yS10JbaILGFArXrPK7mYW6plGpqUpWRuvM9TEVeLCypVXNzVKTPxwJBWsCDZDs6kJWgalizp7CtBKByqqQoOJuliDFWhWdXtPU5A/WEiEBqQ1UrgZVyCUgO6lFGeVcckGlI3oo8kH9p8cFMzOJi9GCaxpJ5Bksd67uSqDqqHdwNzZqjCVlllRUUv+kAQOvzn2EpjZFZbePWemFtQGwUtQ2MbiFUGWNoVo/kW8BuCPItLlmZcNqF5pfpEHyoU+U0ONAy64LuXnn5QJJWPsMMKHTahyYZ4T94BJWg7hGra+cNbb5vK6L1tTXyHrFsqaHikWn3kj9Ofxa5QONIOUSpMXBNWj2i/yRaKMfL/ooW10I0hCgauRQQKjzh+qEulV+OYJIAC6wypb9zQ2y0Ohv9DU2kaBprVDnC4QifqGRaALBxtBqdOyYNutGGmsaggI6eWFuebk0taBQmOv1zCqXphS4ilI/pxRME8qXLi2b5ZFcBVMpvHQpcBcVuFwasoSn6BwQ/9kE9XcG/GWSf1byi34L7HdmKgb+trHrVphFWtmqA+JZjDuLXe3DQjvHnf4vC/pni3A0s2ceVjlubX+caQaz1HmuVTjLrhfC30M/eTgLZ/ersygWHdHQF8uwPsWfQfp8dTxz4A83Z+KMt53x13T/1Ioz30cYHbsj34oz4N8wWs5/0I7yPsnS65bouCBLv97BxhGZbP6rftZxeBmHb+Twcg7fxOElHH6Uw2dzuDpeQ/xKvjy1PfhV/HyDw918+hw+k0/H34PzI5+cFRTvw42pyHiMw60cPoHDbRxeyOEZ/DyTw/l6LuXwPvw8mcPt/PiPw/ty+FIO78fXD4f35/B6Dh/A4U0cPpDDmzk8m7cHDndw+D0c7uTwDRw+iMMf4XB+nL+Rw4dw+OMcPou3Nw4fxuGbOfwiDt/O4cM5/DkOz+HwfRw+gsMPcfg1vB1y+CUcrnD4SN7+OfxSDu/m8FG8Pdf04KM52M7h/HzWyeFjePvn8LG8/XP4Zbz9c3geb/8cfjlv/xw+jrd/Dr+Wt38On8DbP4fn8/bP4Vfw9s/hE3n75/Af8PbP4ZN4++fwAt7+OXwyb/8cPoe3fw4v5O2fw128/XP4FN7+OXwqb/8cXsTbP4dP4+2fw6fz9s/hM3j75/BiXl8tJ+1iPHOgmCuIbdvlTOUGAj5r30mvJ6dZ4VLy8gz4dowuhV9I1+OlxNEkfC7/ci7Q6HoT+wj9MdLochPbCX0CaXS1iU2EfgdpdLGJjYQ+jDS61sQGQu9HGru1xDpC70Eai51oIvQOpNG1JlYQegvS6FITlYT+I9LoShOlhP4d0uhCE4WEfhRpdJ2JXEL/DGl0mQknoR9EGl1lQiD0vUiji0ycPof0nUg7ifyEvgXpQUR+QoeRHkzkJ/RNSA8h8hN6JdJDifyEvh7pYUR+Qi9C+iIiP6HnIT2cyE/oWUjnEPkJfSXSFxP5CT0F6RFEfkJfgfQlRH5Cj0V6JJGf0COQvpTIT+jBSI8i8hO6H9KjifxnkbYinUvkJ/SXc4AeQ+Qn9MdIjyXyE/oE0pcR+Qn9DtJ5RH5CH0b6ciI/ofcjPY7IT+g9SI8n8hN6B9ITiPyE3oJ0PpGf0H9E+goiP6F/h/REIj+hH0X6B0R+Qv8M6UlEfkI/iHQBkZ/Q9yI9mcj/NdE/0oVEfkLfgrSLyE/oMNJTiPyEvgnpqUR+Qq9EuojIT+jrkZ5G5Cf0IqSnE/kJPQ/pGUR+oCu3ZcBISPkMfm7DNaatSG45Cq1bKYPiLt3pOuWJvbRcjL0jtrx3urLa07l9XUWpIHZ2OEnQuWlkqaAch+ifOkbDAG7zhxB1sThJgUBs6c4WY8fWWJft3Ex8AziET5dtw0vJo47RZAlqs8Lxd3TbgF+M7RA7TswULfvEl7qjEHkLjbwfIoux3TT+Oyz+umt+B/5DiA5aDDGV20HAZbszfwqQ5ZOd6F/Elmuay4BBHpUqwtDF204vg9xix5L7liV+DFEco4VEhIab++z52VU76woco+kdr8Vl15UtKVtcVl0lrj+JNwm2YVPZisNHxQlSi7GdbtcZse11eYLY/lAelmnrQ1gzsbcU1JfYWW5HZwYhGf54Yke4FPZ+hSnsEttOyddg9HvwypMk+ofKehLdTaKJnbPzyBKlGAvk1QNqR48IIOkTu0b0XIcfxJtussTgquuUNybnNVW0nZEzPMk5dqSKuQJUfMVEeA9FmCS235e3AS9ikbf0I/m9pdzzlZEcb3hjtXnN3niUlKnQfW8Bl+5nXxLBOORdQDyxTtfrFW1JeUqZ46ldLd2LozZPcjcK/gjweWNJb+yMci/k5umcS3KDkOTmjX3ljUPJPfFrxfhUZRVJ3S1gmfuJyfl2R+tjViybm5WRVRqUa6k3fmteodhyGwxLW0MA756dt8ISh6pp3R69zJNcaI9e6on3EdubladxriCWvOhom5lNSqP84YtkEqsO+BYQviwtn20g8n2u3A18YvuteZViu5y3VCkGb0hIZcFELMUuMX4jXIPC/gALGx0nxm3ahJQBtKavxYRAg+Rm7LbcVOU99gVTUxJTGS+2X32KDB4XENy2u9xOFMMUlEMV9BbKBUZgx7KU0qL94hKNBdP4O13bkS8H074CteGEytz6K2bFX36Rrn0xdmNeDpdO1hdpLSGHT+OpLwxbghj7QZ43dmueU4wHoIRx0GhLswKKegavx6eL8QWKaz+2hcu/QOt51tPydRIVmuNoHQVpYQyv5SgWvpixi507sJfFOE98jnF4G5S6iVW6XocG52gVLai9D8X2uZa/dIMmPCXPOlqHA7gZi+nNPypaOlGSXJDEdcYT+1pxdBMb9rRLOVASizf2jqPtOSLKyyKYVPG9wj22RCeO3DAHVtC3Ueak2y7GuhKv4G+t8ol9Otru7Uct4GooNJrLUkNjhtp1tE4Gv0yMvu1y/BW/SoQWlamsJDoAfZ1JJhP94QoneB2kimXaLi8ROwUUVuwsZcmXsuR3dl0J0UXSzGIvKzshuc1HSbV0Otpu6I8sywyaWBcRs7dWUtKPtpIaKNi2Caky7QfS9Tcs0xjHddsdg3qK0lmaw4qWS/PoEGPePBF8Wft/5eGDAWA66MhywV974jNQ7ZC+GDuhXPs5sUMsQkm94rizxYbRXxPzE6BocC7I87NuTdXMP5NywVPFeCtJn/iWTvqbVpZW6s0IdmWT/oVFcZ3CNlGslVzGtECZojfus3uv8jnl3Iq29+QsD9g99KswKvbGfPYENje1vwF1emNHxfxu7AzBep8mtuiYnfBYdjke3C4+naSf0WJsj7fkhOPBDnuH1+E+UdF2inRw4Bw2qyyekl2Ou3EZaJ7qL+4n1nUVKU7suJh/Tox9JLa83S1aOuRMMZYPVVzyvqP1l2TMvhvK8IFNTO6WHZTNQjTxpTwClTZQjANsFzvJaoXYfh24GdFOugJsjxPElnNWTwwyOOu48ze4KED7a7HtbxjVKsYsYqeVRp0F0fZCfnYZHMEtQKyFZGfZ6XRiux2vQNvEMsR2RLd6Yh90/Yjk421vsid+Rbm6n1ZTv5hU0WlHhz12X14RZBGnQVefuL39h8mYs+1vd4Ce/pRXCKBy8tNksiu/p7+viF+LHdQ40jPk6nqG6MPYK/zLJ9hBkXUzDxStouTT6N9Al92e/JOelve60RNMqGiXM5ze+GWscbwnZ3tj74OZKTd+guamgNP2xiL2ee0Z8LPciZ1brmrd6AwLwR7RcorlXDFZYY+OIM6RL4oPXVw2ptbyFXQ+N1scbTieTGz9FvXheGAJehK1Tg5BqonZiFxwOquSXDobMJ3FgHhjn6Cbz9n2KPQHSl+E677ugZU/gxIS10GGiQhovTdfckkW9SXDPsaeOSmb9eBjsmgPfuojjc9ZDtFIJ/WNTscT240uphC1KYrxCWK81E76GREaVetgYK0j413UAs5GiNdZYvdctcQpX4JjVRjJjhBbdtg9sSX2xDZB5a+IjxNj+7BzIe27U23fX3gsnbr2vddbck5t3+dA2LK/kgY+jm/gnWuaoXGfJY37iU9Ifwc5YEm8+e94Ygc9HeegIPvElqPdXouChSKuuj9xh8dJfcxvv/EzO5oouIT3lWdOg17AGgsrYgWe2HL7/PbZZ6Ey5jjFll12sSSQV+xos0PeXYNBe8o5iE9G0InmLKq4CZ54QUX8drun5fYcIToM3aod66gW0wXF3QhhRezTroHe+NWXYxN3ncLBJ4xQRKV0DHWXpb0NlaIZtKMccpoOlcjirbfkrDdenQfjwOugPj3tc7vFfEXsUCBupUV8+mtaXzPFMS/JQ2AgtAs6tY/XDPG0Z+wAda7pB91QTEncTpzR7Bcg+YNiy/GvxfblX4sdXVY3DI+SO+W+2Du2vG+RhzucbsHhrHCWOQZZ4W+es2xzBml1X1nDV89vv3VH4bz2wK5Cb/7uug3Auw94jzoGzd3nGLTwKNCngRaAPu0Y5BBbOkuhZkvR20YPiCV7HK3/TMa7X4r5O8B8wAWfABe8gxbJhoaVKUI1Twf3apHHopOVs8V4oSdWtEdMdhB32RvV8mVGeIan3bsnR/XHcacY+6EixitBTT88DSHS4MQqc8TYILGlIxfi5XpLuqOvoHrHQrvMiY70xg544lfn0YFH7AOq2vUfoP0ddiXJ7EGMj8zD4cr92HN6Nh974NHBLqkp5nb9zUVGRk7aHjzQFZQoUVEsOetoe56oEpQcJ6oYsFqMPef5XBEte9CGO5SZYseXl4qWHWLDDpymJe7GZkU+Kf8tQknnQxrRGRB/OovfnhFWJ5Ud3ZfixLJhOyYg5ndgz9Nxbqa4/jgBLHvFZGeXpyc9T7IDxkXfNqldHvAAYvJ5R9tQbDOZRPBteM9DmXoKu+LMv8/IhaoqBQU8ss+3QiADvD+DNa37cbEgZ95bXt51MVq7m3DbgLNwK5uWJfc5tp6maX3+IXYqncofPqBeEbS00Bkd6YnPRA0NKFt3h12IZir7TqGiksqhk3S6slQpgJkKWPf6Z3Fme0PZjWXLypaXSct28o7f0boWNGji/BO1Fm1342gN9MJ9XRq31Av3vDTuRb1wX5PG7e6FuzCNu7gX7svSuCf2wn1RGveoXrj7wrUyNs+tiI2/N3PttFyh/J7Z43MS90K/yHWub3zCda5TQYmJPZ9oGJo+4hgGI8PyjzQMj/AMH3UBw11ahupPOYZ9yDBLW4Y7ujmGPyBDY7eG4S6e4X5kkLUMM7/kGBqRYdKXGoY7T3MMXmRoOk3te9sodI100AA9HRk4A+3B4fvr0O0m5+dAl6NOiD5K0AlRIkHNXVTeGgH1vYVMIHYlDlg0iZEp4TbUHIy3HG1PsumlpvNp/WmaZht70exSkgNM77ahchVXF5nD4sRio0AnFji+iTcp4P2Hiu3PEFiZR4pLia3lC0qFLbjYqxxQemAySVNcJzUTmTuJuDvRg7T9Guc9cZqP6/XEdhsVeTkVXV2OcLRW4HCTTCXLrWkzU0frKza9uP9pMxf3YRvqC4qZmPkVOhpwdZjpXywsU1ocbQ7ZWfocaqzmOXjxd2oQPzBlJOMTdMaffF/V9Gc5AlkdWk5GEUt1kskzL3jG0JPZFoWa1YOYWQsYjyDfhKPEHDEp2qMS/RkXvrP85mF+OI1Qct+nawNkfLSKSFbzXUp29H0q2ebj3NAK5XHigDkP5IOxwc7oJayF9V/3Y9KtrGXR1h9Xu5VXh5GVFWVmgoxIiX0iB+on8Wc7XiSrDOqVD5VjeKXCTiyFgNhP7QMwxbETOU7aaIty8qn+Fq+8d67H5FJXHsArS89R53HnCOw2O5VbRnBG5HjgPrRxtQaOgAiJW2w9xcCcPe+TVUAwVkgJ5yWOtgz8pZubtDrTWsvxXmz5JWtPE4XZIO8V9CtlZLlBo+VGjZbnmml5mpGWvzxG1bX/PW6tMVF+jvPBHPffj+FkNyNvRWWpgO5nE/ob4s6mEGucCH4zOgkF2USMBUYy7c9k4O/4nzL2QdCy16LcDdXadRk6gz4WOmXyH6PejESKfQBDKmXHMer2NxMn8Uze45jJbcc1Pu6X76FB7UZttF1qoRWIfDCnS5SofiYzpwDGVDG1RAPHFLAhVuw+UjCsaszECUMnTACf8/jO2tDPSa3SDJqI2p7JO42SlB+nEqNmlYuOobW+rxRAWPqkhfjic4Lqiz8VDHzxq4Leuv5bMLeuR4SeyvHEsrBEj6t9TucctrY+x9i6HK05ad3cB73k9Zpg7JV/8i6dFzS8A41q/5fG9hV4l1rjbGAqbT1FJ6Hj38NJaG1eM0xLHa1/wl4r6YXZXdtv8Wc8I+87U9epd6gidr1NG0MzaQyzTPqZbe+QMfvmiRr76pj4/2hfV79jYl/vvsvZ11PvaJY9Vr1N172343S8gix8uFOLmdtwFq7I77JbKmQRr4J4/AHeWGHqzhGAdojCFkncbGVW8eANBuIdj5DZEnrHl8nqvc47/jnNftvNbarrx6Ql3ybQkdz4o1xHsOVt5o7/8rXqjp/42sAd/9qqz3BtL+641kTlfz9Kjfjf36J+cAP4wa2F8LWl0lsqoOnsIZUbyCvke55hb9Ouuun/qKuedpQ2m4FvUbttol31jXn1/0cZPvsWzfDnR2iG9WqGeE8CxwaQ4ajU0PsgK16QcZNbk+ymGxksFfYMlgq/y8HSpW/RwVKh8smbdHgG02iR3JwhOV5Df+pynKvJcYxZjg4c09x81NiR/foIzblYWfsmmsyHStlRMvpxnUqMNHF+oSPUuOa+iWObL5LJug2a+832Pui9PxNjV+eVrbvNLjhaX8vApnWbc+sEmBi49j+NK+iKiFm3dCcdrTMyNbf3Qm+qt1hGmN726RDRn8bsbleyq2/dBs/6TgHvO6trjHd42jP6iNckbZgmZF7m8H7uwXlR3IljPacyH+u5bbuj9U5Bk/cnb6jTEbpsOQGXz9plGEu2P5SnwLBf+bc3jW4svknKEy+GUYGyELUJLusKsgaelzYfa/s7G05kQWbqehKWrVjJgzqBUrWVkGFWRp43XkgmW/UKJPgXkpVjwZstzd1Cc39UwbNHiAvBIaRdbPdemrx3pJ2T5vI31LtEZc8QcSY6th6g61x4B/G+vNMokfQGuWOvuVfkiZ2siH3IJXX4dV3FbN1I75JixXRjMve8YVgxZMUtfp2Ct9wr2oOK56olStSBt8yHv0mEfWhnl5XceZRzSIUNZvfvdsEECCrp7cPoON+T+5DOVB7W+npF7GzXJO36mb53BZboLHRzv4bYra/jApbd0XoQ1+qP0Bsg3akHK+qJ0Zwuc3RkQe+YAcYbp0HXdZoGVsc3MMJGg65qDdsKM7YFZfGsdjFZFssGoR8YQ24wfIiNCp9GU0ZA/SYGJDVLClex2xKE4QuQJJGvZfjzWY7hEDL8B7m3CpWx/llshtziGAxAyWLBPkFdLNgtGC0WzEzrgIbpOiBOqIRA5ua7u26DL7Wv67q5h3hL6WD6u4HoL1qtV5Wj9eO0cdtzFvMc/4cMmHvSrznMJI6TJwEaiE/3XUAnwutI751Jxd7xGu0WrjvEcuoU6NMdnytDQWt0maTfYdo+Om3qnCM3Q51zbD1MBzkE6Y9rI/jgmXL3a1R7EzLo1CEHQmXWYc3UwXeI3LuvaEs62m5gcy/kA7+XWIPP9ZAM2l/TZ35Pppp5GcucIBMx8+GkvCzzDZk083UQKrte02R+/NWezOeyzJEPM/eljzxIZS06RBc1roC4idr06RlhmnSIjl8zkWkmMHWhShMrqWphrDpgDB2rYo3BWHXYmJ6xKoHwLndGz1i1KUO/QvNE2rjtbsHUprqiNNeHc2muWFWQ669ye3IlEOSK1aXmeihTN0K+Q2NkPzLLba5RlYx4lY6QUSx1hLwCDaLjENVfMxIPAVfXtUbxDx+k8bGAavznUKfrWXx8jUOpfpWacoCF8qu0K/cS06am5Yn1wYTwJ514aR9qMph4/SGtstt6qeyIakYsI/x5nhn9Pc1TPNqLp2i3GJvoH14h86HHR2ls7IlRF2Zj/5BL+cErJto+cJDT9mOvaOZD1738jfOh2oOG86FivL0C86G5ZvMhMVZux2beWktmrQuhd7ieTFq1N6hbr0nrHIb00jmcg1wS6020kP8y0cLYSzVtbuKlF9jm/hEtPHbApM1UvMK1mdyXNVp4af83auHIy/+gFgZYVC1YLQZaOJbW3v5i3t4SjwnMq6rz0gde4ualYw+Qm2+QKD7ASPJ8HX/p8/xdWp7remnjQaPqnrGf3shzvITVbtuOc9J1C0uFrh8Ycfdl3G/vI9zaGSz6LvsB485l30s04uMQMeH4ijwfW7akSmw5meOJnfPEl+fiOGEiGSdcnnaj/nfs6dGb9uHMeQ59qiK+PKe3OD9lcabTODksjrO3OK0sjpXGoYPu+CiMMpZEGZmals7cT531qy+mnuARW57NuaFsueaOp7y4RxvevIw4/HV5NAw/5BkGAMOALreGYQHPMBQYhnbN4oabuFotthflKY1YtQfPacaiX5GLcp5dWYhXT2qvDkrSq07FhVetQPLj9575YyXoiD7N5Ggly4DJhTmOtl+S2hntiYfsYkmXvLrsGazIrmJN6Yeky881+/Gk5P8Dddg1coM3PrECmu9YD044RnrYINhb8n70v3EO3LiX2Byt6Z2Q5ZvRFyB7VI4dNVGxl5qYey+vETs32tbd31+MBrj+5DoywDlHpnQ5aLD4xkjqgeVVUDax5OcElAfACB7ZQcvLdortN+bZyXAO+UJQg1vfhtnXlnyGXPMiXUkiQ2C0HHx8lixq35phj8sZE3A5ezOKnoPsv9xLb3mALEdwDfsc0Ltb89ZAduMpDkVDCrdPEZS39qqD3MtfJAvZbEJ8dZ7y0It0JRiqFocRr7wAM/dTW/GtyS24tQR5fvJFOjaNZ84Yjq6eFG1g+XDVz3sz7LjW4qQefnbe0vN177daiL/BIM29N+NyYucLdBnHSX073mCTX6SSr1Dm7aWNahEtXtcyUsbzX6P9xtw9L5ClYUerNUnHWHbIMfHZOeKPqsTYV6nR+o/tytfkmfy3bkgceMHw+hv0uvKnFxjf889jA0rZl57/vxh/q8r/r73z38r4q1X+m5E/xb6hUjkMV5Qn/46lmy0I0FxjybIlntiZssWe2Ctl1d72yzc5c4XFYvukzRBWefOPwZy+46wN36xSfrGHroiMUhP0xk54Y2dmQxrJoW9AE7NAq46eIG1omdqIdnLl/WQne0eLvZKF7x1PrvWvnhyRaxuCQm4/gX/N/8orI9GV8FMH4qv4oSBQUZ+cG4wGArnBkJy7uibQUCs0BEmYG2iQ/eGaQG5dKJwbCAVXTcjPXdMg1+fiG+y5rsIrxwueyQtzQ03AhK+u58J/8sZ4bW5dQ8AvhCcKcyDMHYMsQZIKbhIC2QvloWigNjheZleQq+f9swWuKdJc78JZZV5JWiC5ipvWyvWhYINvGr6LH3EVLqkJRP1u3KnBfT78U6vkmmAtbpfAovTOX+JWX8V3n195ps6C6uAjOdn7yqcXlGreg069t8mub2fXcxeWGl7fwK6Xmlxfwa6v0F3vvbwzPAu5ujsP+aa7g6sbwqFgoz8o62Jqy7NvoXF51OsbGe6sLDXcP02tBxzTkPc3Wajfryf1fmqlln/jN/Cv06W/T8dvucR2VSt793lCZzKJi0ObobE+AqP61yDEe7vPgSvAdzQOQYgvH4gnkknsmZQzySS+c3BPdzJ5CML6L4AP4jXDkAsfzHoEwkoIn4MQ34TshnAdhMXgazZB+DiE3eyl9KHqvoW3LBIszU7LJQP62DdY+jiHsveLXVAW/r1YY376Li/yV+5OJjdg/53tnJOdM8/Rf419nTBzxFVXTM0by8e36eKr+W2C/Ph9Akem+Cu9JEYfG249ZFPjFbH3iO+BeMFRgpBxsqpUKMt2zsrOmZWdOyt7wqzswrLs4rnZpzNa+tyX1Z55f8YDtrusJN6N2C6UZPIXAyDezxcbx9uerYmH5XkWdfZZMvkQdtKzsp1l2TmzswtbbPdbaXnew/dsQUcvkY240tIsyy7VJEk+eWxvrsrPk8mBuBODvEQtT1l27tzsjbaWjPuBG+tpNuRbDDq/lKXfYqX1dyPgpYBfrsNlwJca4PcB3mSA/zvgOc8lk2MYru4D+TXg64DfL1C5H7C6s3Put7mzc9sz3NkT7ssUswvvyhKzi1v6VGSXBlBSkHcCkR1qAGSxk/Rnow1COlZdm0naftuybp1g22ibyN7CL8OvmxixBL8+YO/Pj0NF+Cz05f4mvIL7VWBr+ttgtj0fvlP7EhLPsislyPuRlab2IH5Ns1Hiv/BrvY3G2Q2EZRPb52ovEknG9jl+Dc0QhH9St3r4TSbd1iA2CNieY8RP8G3cF7Lohg1HkHD3pakdROLGvjSfIL40DB2o8CCE/4ZX/ghEvVobI/rTHRzG47vDVZDuclWEJ4DYrG4e0TCYvoA9B69MHsJ2zECiCL4OqWwDhtMSzMc1yNnD6eYWv0eiBb4kle2dEXQbiGZ8YXfoSBpn5ihW4aJVs9tp0nZgvWDbR4jDarEPM22F8BFnfFYRZcDny4gZIkH2zvythe6PYEW2Tyw0jgMJfFPRrpbHybZRK0WfMDaTvnM/D4kFmdwGHequkbPwyq8Y23Ykngfiz2pqd/al0o3AL3t/SmzE+h0MX3FLyg73CbYFZNdSNQP8gfdMk0h08HtNHGAbavwSY7/Fdk34tYXxZluE7z/ff77/fP/5/vP95/tPar+ckWw+xPZxrxypnUdZTMKDmVr6qI4+y2h1b6qjw2m66p5UrRWUvljdf4ntI67usaTuOaXu0aSw6+o8RN1T67NzyRDZf8damtoXjOyv07c0tS8anbhQWt1bq4NdUPfUUveIGqarH1vPRlxsPzq271Gmdh6m7v2l7kG1cXCpBn9kUKmm3HZWUX11+Z9LUnm6nZQ/yWi1HKcZfZOz9P/VTlL72Os+F+XQcoxj4XQWzmHhEhbWsXA1C+9i4cMsfIyFT7FwNwsPsvA4C8+wMIvN3y9i4TgWTmfhHBYuYWEdC1ez8C4WPszCx1j4FAt3s/AgC4+z8AwLs9i+uxexcBwLp7NwDguXsLCOhatZeBcLH2bhYyx8ioW7WXiQhcdZeIaFWay9XsTCcSyczsI5LFzCwjoWrmbhXZcY28/c8vIrcycsXhkNytHcooLigqJJU6KEct3uKiooLCooyqe4wJh8gZrgqtzV/nAElwOnFkwrKJxURKNMuV0ORyPy2im5E+SaVZHJi9xed1mVW5o6rXByHW6jmZ87AdcVa3EV0etdUkGj5wtCQWRto1yzEkI5TMN69VdDUPaHm4SCYEj2F5TN8kyCpBm1KhgtWBltCNROaqgVCFVfE6kXCmrXBiE9GspheoUVWENIcC3sD9QgI/vVFJAxywb4lv3N8A3lboBrodoauUYo8NdLdeGaRr9UXxvuoSBRn49tYSrJZLtkkoZUEw7XrKVpqL9v8oVJwWoaG3wQLySTL5ovzWNlJCIU+EKNuBb3D7fjS5iPVv1Yz3ka2nUevf9XP5cJ2r0Ue86rYOt5Ov4MHe3SxZdZfJlbf+ktPq5/nAEfqMZX/f4jDKhleKaun0itezKfb9X1C6qDfZz1C1lMdrvOPy9hrFZdP/N4X22/YlZ/y5lPV+Orfvwm1uHdryu/7tgQ4WbWR6i02k90s/gbhZ7y2wzkv4XVqVXXLz0ySNsv6etPlb9VF1/t5zYO1vaLmazv18e/X+g5Y4UfFxwdru3vzfQf08UXWH+gZrDBplun1oUP6eKr454NbODxscs4vvr5mS6+Oo5prdD252bl36hrfxtY/A0svmjrPf/HdfF7zn3p0U9v+T+li7/ih2z9ni2x3KdbDNTbz3ZdfFzmpSGl37D2nv9+ga7N2XTjPvVcGb28+vyPsLV6m25cqCwz5tfTJ1j5U+MpFv/0ecb/kGtb/LhIPfdHrZgsXXxVrm5d/ur+vd1S7/mr4VldfHVcKrDgkKX3+FkWbfxDbD/IQzXnV/8D2OJhKn+2D7DC4tt19qvvDwax/At1uBr/LpP+Rw0HCdr9etVPcCXzH5be/S9vu/xHvJm5EbYJLi61zjfwX31N8l9xC5tPDOo9/94+NuBW+2Mtbk31s1rcluo/tXhGql/U4pk9/Z0Gz0r1Y1q8j+E8wwa10m2I9031J1q8X6qf0OL9U/5fiw/o8esafGDKX2vx7JQf1uKOlH/V4s6U39Tig1L+UIsPTvk5LT4k5b+0+NCUX9Liw1L+RotfZDi/ssFsUvUPWjynp91r8ItT7VmL95yLosUvScMsxGd/lNTjdI/a9HpwMxxv2/Gf6xiOt8/4TwNpfz16VPcwXk/yHiFk6s5X2cT41fu26p7EbzO8SYcPs1Bcvd+r7sHsYfj2uRR/iGUQYfhGXTobGb7CQ/GXGP4pw3Ovovgv2ALHv1gpXjqPrXMwJ4P3vFCuDJ1cBwjuSN2fVv2LzUbxXB0+neErdHgDw9X76yr+K4YX6vDnGV6qS+cLNX32fIG6p3J+BsXV5xrUPZJvZPgGHf4Aw9XnAtQ9j3cxXH0eQN0T+iOGq89FqPe4R2dSfFOlln8hwyt1+J0MX6fDf59pbM9PE/709rg7k+rxqM7PvM5wp2597AOG69fNMrKo3i06vQ8heLp/wHOTiD3r0plD+NP9jJlcfsI/SFB07TSSZSyvYNLe7yD86X7mn8nAZkha+R9juL6cT5N00v3bjiwcG6T7qxfMzssywXP6ID5QWMf8vNq3T2D4Ezo9Tu5jfE5UsI9x+v9kgv+lj/E5Y3tM8CMm6XxsgjvsxngpwdP7uzkm/Deb4HeY4A+a4E+Y4G+a4OdM8Jy+JuekmeABwMdaBwoCk1ddr23pa3zu1m6TdF7ra3we17m+xvrCW9ODuPGDOo/J72dyLqIJfr0JfrcJ/q/9jMvzZD8cm6e3lx0m6XzQz/jcsyH9jfmv7m98LtnK/rQdbRypXU+/o7/xuW2PYjrWiwVFV87fm+S7t7/xuWfHTPitA2j6R3XpOwaYnC83gJbfyfToV8czJvwbTPD/GGB8Ht1OE/5jA5BnRFo9fGTCP2Cg8bl2ZQON+WtM8LtM8N+Y4M8NNLa3Nwcan49nyzZOZ7gJvsIED5vg92bTerP7tfX2gAn/yya4km18bt5Yh0n7dRif+7fGhP+fHbQ96vX7c4fxuXx/NUlniNPkvFMTfJYJfr0J3uw0PrfwQRP+/zTB95rgb5vgOFHHdreJ+Y0gO/Qkk+AG877J4VBInty0tkb2hWr94clN4dDKgL8xMjkSbWwgtxGmFLpKJrsn4+lTBb6mJnL4FL/G7kpDpqQh04XUU6+R6ErJI6VSk643eyTW5ZIkvKsgNwQlyVu0IBSkR7+d9xPLswvp2V4X8kjxt4oz5TziFOGD1+fFqT40/E1FicoNAZA3Ul8T9tdKYX+dp0qevtrvk0Nhz4KqQommRo6+q6rxVE2T3G63WoD551PnpMgz6qJBTLIYHycPNAT9voBn3qKe9AmTG5Ou9gUi4V5ScqeSiDQhK5Ss1j2jLhReUxOu9VRL7romUsSmhVUlUm+F7BHMtzrAzob0FktSQ4jcMMJzBi/ksfbz4Nc/dn4+UXRPwp9HFIOHv785Vs8j5t/MW6IVoeoCa6nqwmup6sJrqepb1VLVBdRS1QXV0pILrKUlF15LS8638L6wHJGjdXUFPkGS5pUvkryeqmpJEnpOkZXkRsmHp8VGBANIkmpD0qpAaGVNQKqFRh2RaqLNgi/U2BTwy/7aguklxVOMmaSee6cSVHx4rUDvv9ZGGxvXQhSOknpuuTJWSZqzqKzCLbkXzMazcEnJ2W8m9cI5c6rc1VJ12SyvGzk0SdRqAXIYoiDN/tGCsgpPuYA3a1VMf0BnaSl/xGHvB5rqeOnBi75IlEgupHK4wLM99SUwPPY2rZiGB/NquApKzuuIYXKMZXry3GGZBlXUy9m/2jK4XAKrHeMDN7Vp06MtGcZOqiTnZWqhtCMvdZd7PeFUL03aWaF6Lfecx5mejcm5vOkqNT1DNy03fGYDdB4ISKkTh7/dCcPalMkhowYCpJ9ArCtRr0dQL5TIS25SNOKvTT95WFeCsN+fVoDezgfWRqfno+oS6OUMbH2jNz3m2si80w6ANXQTRqdYG7QkgzNq05NzFUkS+nSwC2LSUysWzvbRoYvBmch6qwHZVXeZdiJ0ujGSg4TTYe6Ia336tZGQVA/dMNQsPbnWsEGiK2Tjq+/wKG69U2MH3+pNSXuUtF669EOY9SKujEQ4c0mdQ65P6PwOJy4t5Q7YTT9S2dDFpJ2vnJ6I9gxqo1S0B7xrUzA8Ft7kNHWdXybnEBt4j293qrjOL/hDdXpzSp29rpWAdPTf7mRvXZ7kxdg0Ezrvg7UN+myD0+7NfIHJoeVG+uROPddVBXkCzei48nSz+Q6O5TboNQ2kY91fmhfUnIUN19jZ1Pqj7tNrVT213GD4Q88dNyiE/lD2dFNuWtujeVdR+tne+kFJQ1Cgfu1/Aan6BFNriwAA'
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np
i8 = np.int64
i4 = np.int32
MOD = 1000000007  # type: int

def solve(A, N):
    x = 0
    y = 0
    z = 0
    count = 1
    for i in range(N):
        if A[i] == x:
            if x == y and x == z:
                count = (count * 3) % MOD
            elif x == y:
                count = (count * 2) % MOD
            x += 1
        elif A[i] == y:
            if y == z:
                count = (count * 2) % MOD
            y += 1
        else:
            z += 1
    return count

def main2():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    A = np.empty(N, i8)
    for i, c in enumerate(map(int, stdin.readline().split())):
        A[i] = c
    print(solve(A, N))
'''

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=1000000007
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    c=[1,0,0]
    ans=3
    for i in range(1,N):
        tmp=0
        color=-1
        for x in range(3):
            if A[i]==c[x]:
                tmp+=1
                color=x
        ans*=tmp
        ans%=MOD
        c[color]+=1
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=1000000007
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    c=[1,0,0]
    ans=3
    for i in range(1,N):
        tmp=0
        color=-1
        for x in range(3):
            if A[i]==c[x]:
                tmp+=1
                color=x
        ans*=tmp
        c[color]+=1
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
c = [0 for _ in range(10**6+1)]
c[0] = 1
r = 3

for i in range(1,n):
    k = c[s[i]-1]-c[s[i]]
    if k==0: k=3
    r *= k
    c[s[i]]+=1
print(r%1000000007)

Submission status: Wrong Answer

Solution code:
n = int(input())
L = list(map(int, input().split()))

mul = 3 if L[-1] == n-1 else 6
MOD = 1000000007

ans = 1
available = []
for elm in L:
    if elm == 0:
        available.append(elm)
    else:
        counter = available.count(elm-1)
        if counter == 0:
            ans = 0
            break
        ans *= counter
        available.remove(elm-1)
        available.append(elm)
        ans = ans % MOD

ans = (ans * mul) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import random
from operator import itemgetter
import re
import sys
from itertools import accumulate
from collections import defaultdict
from collections import deque
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
input = sys.stdin.readline
N = int(input())
A =[int(i) for i in input().split()]
num_count = [0] * N
ans = 1
md = 1000000007
for i in range(N):
    num_count[A[i]] += 1
    if num_count[A[i]] > 3 :
        ans = 0
        break
    else:
        if A[i] != 0:
            if num_count[A[i]-1] == 0:
                ans = 0
                break
            else:
                ans *=  num_count[A[i]-1]-num_count[A[i]]+1
                ans = ans%md
        else:
            continue
if num_count[0] == 2:
    ans *= 3
    ans = ans%md
elif num_count[0] == 3:
    ans *= 6
    ans = ans%md
else:
    ans *= 3
    ans =ans%md
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=list(map(int,input().split()))
counter=1
uselist=[0,0,0]
for j in range(n):
    human=lists[j]
    if human==0:
        for k in range(3):
            if uselist[k]==0:
                uselist[k]+=1
                counter=counter*(3-k)
                counter=counter%(10**9+7)
                break
    elif human!=0:
        sub=0
        for p in range(3):
            if uselist[p]==human:
                sub+=1
        for q in range(3):
            if uselist[q]==human:
                uselist[q]+=1
                break
        counter=counter*sub
        counter=counter%(10**9+7)
if lists[0]==0:
    print(counter)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

N = int(input())
A = list(map(int,input().split()))

data = [[] for _ in range(N)]

for i in range(N):
    data[A[i]].append(i)

ans = 0
if len(data[-1]) == 1:
    ans = 3

for i in range(1,N+1):
    if len(data[-i]) >= 2 and len(data[-i+1]) <= 1:
        ans = 6
    elif len(data[-i]) == 2 and len(data[-i+1]) == 2:
        for j in range(2):
            count = 0
            for k in range(2):
                if data[-i][1-j] < data[-i+1][1-k]:
                    count += 1
            ans = (ans*(count - j))%mod
    elif len(data[-i]) == 2 and len(data[-i+1]) == 3:
        for j in range(3):
            count = 1
            for k in range(2):
                if data[-i][1-j] < data[-i+1][1-k]:
                    count += 1
            ans = (ans*(count - j))%mod
    elif len(data[-i]) == 3 and len(data[-i+1]) == 3:
        for j in range(3):
            count = 0
            for k in range(3):
                if data[-i][2-j] < data[-i+1][2-k]:
                    count += 1
            ans = (ans*(count - j))%mod
    #print(i,ans)

#print(data)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(N, A):
    M = Mod(1000000007)
    ans = 1
    rem = Counter()
    c = 0
    for a in A:
        if a == 0:
            c +=1
        if rem[a-1] > 0:
            ans = M.mul(ans, rem[a-1])
            rem[a-1] -= 1
        elif a != 0 and rem[a-1] == 0:
            return 0
        rem[a] += 1

    if c == 1:
        ans = M.mul(ans, 3)
    else:
        ans = M.mul(ans, 6)
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ar = list(map(int, input().split()))

dp = [0] * n
MOD = 10 ** 9 + 7

d = dict()

dp[n - 1] = 3

for i in range(n - 2, -1, -1):
    d[ar[i + 1]] = 1 + d.get(ar[i + 1], 0)
    dp[i] = d.get(1 + ar[i], 3) - d.get(ar[i], 0)

ans = 1
for i in dp:
    ans = (ans * i) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

l = [0,0,0]

r = 1000000007

ans = 1

for i in range(n):
    if a[i] == l[0]:
        if a[i] == l[1]:
            if a[i] == l[2]:
                ans *= 3
            else:
                ans *= 2
        l[0] += 1
    elif a[i] == l[1]:
        if a[i] == l[2]:
            ans *= 2
        l[1] += 1
    elif a[i] == l[2]:
        l[2] += 1
    ans %= r

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
lists=list(map(int,input().split()))
counter=1
uselist=[0,0,0]
for j in range(n):
    human=lists[j]
    if human==0:
        for k in range(3):
            if uselist[k]==0:
                uselist[k]+=1
                counter=counter*(3-k)
                break
    elif human!=0:
        sub=0
        for p in range(3):
            if uselist[p]==human:
                sub+=1
        for q in range(3):
            if uselist[q]==human:
                uselist[q]+=1
                break
        counter=counter*sub
        counter=counter%(10**9+7)
if lists[0]==0:
    print(counter)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

ct=[0,0,0]
for i in range(n):
  f=0
  for j in range(3):
    if a[i]==ct[j]:
      ct[j]+=1
      f=1
      break
  if f==0:
    print(0)
    sys.exit()
if len(set(ct))==1:
  p=1
elif len(set(ct))==2:
  p=3
else:
  p=6
print((cmb(n,ct[0],mod)*cmb(n-ct[0],ct[1],mod)*p)%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
A =[int(i) for i in input().split()]
num_count = [0] * N
ans = 1
md = 1000000007
for i in range(N):
    num_count[A[i]] += 1
    if num_count[A[i]] > 3 :
        ans = 0
        break
    else:
        if A[i] != 0:
            if num_count[A[i]-1] == 0:
                ans = 0
                break
            else:
                ans *=  num_count[A[i]-1]-num_count[A[i]]+1
                ans = ans%md
        else:
            continue
if num_count[0] == 2:
    ans *= 3
    ans = ans%md
elif num_count[0] == 3:
    ans *= 6
    ans = ans%md
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

mod = 1000000007
fmax =-1
smax =-1
tmax =-1
for i in a:
    if fmax < i:
        fmax = i
    elif smax < i:
        smax = i
    elif tmax < i:
        tmax = i

a = a[::-1]
result = 1
if tmax == -1:
    result = 3
for i in a:
    if i == fmax and i == smax and i == tmax:
        result = result * 3 % mod
        fmax -= 1
    elif i == fmax and i == smax and i != tmax:
        result = result * 2 % mod
        fmax -= 1
    elif i == fmax and i != smax and i == tmax:
        result = result * 2 % mod
        fmax -= 1
    elif i != fmax and i == smax and i == tmax:
        result = result * 2 % mod
        smax -= 1
    elif i == fmax and i != smax and i != tmax:
        fmax -= 1
    elif i != fmax and i == smax and i != tmax:
        smax -= 1
    elif i != fmax and i != smax and i == tmax:
        tmax -= 1
print(result)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split( )))

cnt = {i:0 for i in range(-1,n+1)}

cnt[-1] = 3
ans = 1
mod = 10**9+7
for i in range(n):
    ans *= min(cnt[a[i]-1],3-cnt[a[i]])
    ans %= mod
    cnt[a[i]]+=1
    if cnt[a[i]-1]<cnt[a[i]]:
        print(0)
        exit()

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
now = 0
c = [0 for k in range(max(A)+1)]
ans = 1
MOD = 1000000007

for k in range(N):
    if A[k] == 0:
        if c[0] == 0:
            ans *= 3
            ans %= MOD
        elif c[0] == 1:
            ans *= 2
            ans %= MOD
        else:
            ans *= 1
        c[0] += 1
    else:
        ans *= c[A[k]-1]-c[A[k]]
        c[A[k]] += 1
        ans %= MOD
print(ans)