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: Accepted

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

gz = b'H4sIAJ/d410C/+19e2ATVb7/JGlLeDUBESogFC0KIqWFAq2otJTABFKotCCrwtCmKY2mTW8ygaKoYFvXGKvourusv13l7r3renfv7uo+XPCBvIuiiC8WxUdlRSeWly+soOR+v+ecSc9MZiq43vvPzyg98/3M9zy+3/M93/OYmXNud3lmWS0WQf1ZhasFpJ4YVkzoYobf5U2yAFYo9Ia/I4XhQgbQ6RxfsVCsCbtY0mpoZ3w2+JcG/wqtlC60FmvC4YxPDS1cmC7wv2JNqCwSNKEgZCfjYVkPLKHogSXLNKEzjeJ5vbTxrCxeF4vXxfjVULAKmlCVL439q2R4JZNLDWcyvpkcP/7KD8s1eJ11DaWzrinWhKsZ32pdvGsgXoZw9j8nCxew/Mz0MoaVXw3VepgQ8FdPKZgQqBkf8DdEmsY3FU4ZP6UgNxzMnUjK5GS8s+ct1Ogxi5V5ELMBvD+n8tlA1/3eK3698vGH0z9/33Oo5ch/470iFg+rpLXBWZc2qrfVIhQIayBpvHcl/CuBf39+e9Ibfdauk37lfXbnvfWJ3Xe1ege/XrGh+Z4fFX8y/hNpaWb2irwxrjc8Wz6+ZMug9f1KHx7euHGV+6Yne9LPB1CAgQb4a1ZjfILFGP+zYIw7kxam/Y00wV9ON07nVhN8j0m+bSb8YoYx3ssEv9YE/3GaMe43yfcSk3QKTfT8NxP8ApN0Jpnoc7lJOn6TdD414R9pwj/fJN+fmNRLuon9VJrk+5QJf3+T8iwz4Z9vwn/SxP5HmaTzqEm9bzLBnzJJ/zYT/fhN9DnJpPyrTPQ2yIT/jyZy1ZuUs8QknSMm5S8ySeddE/3IJvgLJuU8ZtK+LjXRw6sm6e81KecVJvI+a5LvxZDOKGGo8Hg17UeyGD6Q4Se8yzT90KXpFBdqKL6Y4X3TGM7SWcPw37B8111QrMl3NtPPsqFafC7kOwDS6WDpq7Z0cxrFBd8yTf/2poXmu6Zay+9g+szT5VueTtPZUK1N5yqWfgfDnezGbCbXshqdXEz/J3TlF6C/Dcs13nHjsI+dIkjS8vpggxSWq0KyJAnSnBXSAt9yf1j2hUoDVeGwLyxI7soyqcYXYnBlWWkg2OCrrKoO+Og94ztSo1wX8lXVSDf5VkleuJIR9DZVSbUhn0/yNXl9jbI/2CBI182rCBdAto35eRLmFJZDwVWuBXMrqtxeF7kdLIIb/oawLyS7Ay7XgopgpYQ35lbIk73yqkYfMOZPAp6V/hpfA3D6ZdcKYKiQ86dKEpQjuFKqhqJUBQJB7woaM5w/qdbfUCPV+kNhWQrWusrneuvraXaTawORcJ2axBQ+CW9VWCYpwI1JoUiD7K8HYUKhYGhmPhchCEL4qurVQnsBzffWVYUkOVTll8NQXpACUqiuCvu9Kre7UqrMk1wVU6TyuRWTpADTF8mcpFwEWq73N4AqaRHCpfmopzApd2UlJFjUnaC/YTlL1iB3oluqXLnQHwyDbGFfgRsUx8QAfAooqyrg6wZ0ArPMkyUBBfKVhlC9BpFZ6SA/Q41M9gZ8VSEX3JkouaFM8E8mZgOiT8xTayEYweqSQlUNy32QpVqbU0htgs3KUkNQW6F4eypX2br7lW4oGW+PCOhkZVVRDabeADYge+s4u4WyVUi++kZ5FbSFRmhMwVDVcp+LWWj+ZCo1rZLqSK15fUwCHlS2tLypSWr0hcLBhqqAH5JdkccUmCzmzImsVsKgrDIJFHeTBCnWqOiUqsZGX0MNERKQmkD5CqgKuQhkJ1qUUc5F51Q6Ug8FXtB/alwwM5O4GK1hZT2JPJXlzumuCFRHvYOrvl5jLEmzpKIS/ZMGDLw69xGc1BiRXV5mpefWBsBKsbaJwc0HldUHa3xEvnngjiDTpqpq/4p8NL+wX/KiT5TQ40DLrg26eOeVD5Kw9hlgQqdoHJinhnzgElaAuEatr5Q1trl8XResrKuS9RXLmh5WLDr1eurP4Wq5F2oEqXxBWtiwEs1+gS8cqffhTS9lqw1CGgKoRg4GhFpfsFaoXe6Tw4gE4AZTtuxr8stCva/eW99IgsZVQq03EAz7hHpSEwjWB1egY8e0WTdSX+VvENDJC7NLS6VJuXnCbI97Rqk0MTe/IHk5MXeyULp4cckMt5SfO4nCixcDd0Fufr6GLOIpOgfE/2yCep0G/9LJf1ZyRf8K7Do9GQOvbey+FWaRVrbqgHgG485gd3ux0M5xp/6XAf2zRehI756HlV+yqi/ONBsy1HmuVfiG3c+Dfw/e/7MMnN2vyKBYZKi/N5ZhbZI/jfT56njmtT/dlI4z3jbGX9X1cyvOfNczOnr7WCvOgH/LaHnsA3aU928svS6Jjgsy9OsdbByRzua/6m8Nh5dw+AYOL+Xwxzm8iMM7OHwmh6vjNcSv4MtT041P4+cbHO7i0+fw6Xw6vm6cH/lkLaN4L25MRcZjHG7l8DEcbuPwPA5P4+eZHM7ruZjDe/HzZA638+M/Du/N4Ys5vA+vHw7vy+F1HN6Pwxs5vD+HN3F4Jm8PHO7g8Ls43Mnh6zh8AIev53B+nL+Bw8/j8Mc4fAZvbxx+Podv5PDBHL6Fw4dw+G4Oz+LwfRw+lMMPcPhVvB1y+DAOVzh8OG//HH4hh3dx+Ajenqu68ZEcbOdwfj7r5PBRvP1z+EW8/XP4xbz9c3gOb/8cPpq3fw6/hLd/Dr+at38OH8PbP4eP5e2fwy/j7Z/Dx/H2z+GX8/bP4eN5++fwXN7+OXwCb/8cPou3fw7P4+2fw/N5++fwibz9c/gk3v45vIC3fw6fzNs/h0/h7Z/Dp/L2z+GFfH01H7GLsfT+YrYgtm6R05XrCbjDvp3eT0y2wq3E6DT46xhZDFdI1+GteEcCfqNPzQYaXW98H6E/RRpdbnwLoT9GGl1t/HFCH0IaXWx8A6HfQhpda3wdoV9FGru1+BpCv4A0FjveSOhtSKNrjS8j9FNIo0uNlxP6z0ijK40XE/p3SKMLjecR+tdIo+uMZxP6IaTRZcadhH4AaXSVcYHQdyONLjJ+4gzSdyDtJPIT+makBxD5CR1CeiCRn9A3In0ekZ/Q1UgPIvIT+jqkzyfyE3oB0oOJ/ISeg/QQIj+hZyCdReQn9BVIX0DkJ/REpIcS+Ql9GdLDiPyEvgjp4UR+Qg9F+kIiP6EHIj2CyE/oPkiPJPJ/g7QV6WwiP6FPzQJ6FJGf0J8ifRGRn9AfI30xkZ/Qh5DOIfIT+i2kRxP5Cf0q0pcQ+Qn9AtKXEvkJvQ3pMUR+Qj+F9FgiP6H/jPRlRH5C/w7pcUR+Qv8a6cuJ/IR+COnxRH5CP4B0LpGf0HcjPYHI/zWpf6TziPyEvhnpfCI/oUNITyTyE/pGpCcR+QldjXQBkZ/Q1yE9mchP6AVITyHyE3oO0lOJ/ECXP5cGIyHlC7h8DteYNiP5VAe0bqUEirt4e/5Rd/SVpWL0kNj8wYnySnf7li1lxYLYvrWcBO0bhhcLyocQ/XPHSBjAbTwOUReK4xUIxOauTDF6eKV1yfaNxDeAQ/h8yXN4K9HhGEmWoDYqHP/WLhvwi9Ft4taPp4uWfeIrXRGI/BSN/CpEFqO7aPxDLP6aq34H/kOIDFgIMZXbQMAlu9J/DpDls+3oX8Tmq5pKgEEekSzCoIXPnVgCuUUPJ/Ytid8CURwjhXiYhgtLri1ZVLKwpLJCXHsEHwo8h01jMw4XlWyQUoxud+WfFFsPymPEtgdzsAybX0dNRN9TsL7E9lI7Oi8IyXDHHX2XS+Hd05jCTrH1qHwVRr8L73xBoh9X7ifRXSSa2D4zhyxJitFATh2gdvSAAJI+sHNo9324IN7zcUsU7uYf9UTlnMay1pNymjsxy45UIVeAJaeZCB+gCOPFtnty1uFNLPJTfUh+7ynrTxvJ8bYnWpPT5IlFSJnyXHfncummU8E45LNTiYQ72p5/sKw1IU8scTy5s7lrYcTmTuxCwdcDnyea8ERPKg9BVHf7bJIbhCQ3T/S0JwYld8euFmOTlJWnMHWXgGXuIybm2h0tP7Vi2VysjExpUK7FntjqnDyx+VYYhrbEAN41M2eZJQaqadkSudidmG+PXOiO9RLbmpRNODcQi152tFZkktIoz32VSKDqgG8e4cvQ8g3pj3xfKj8HPrFtdU652CbnLFbuAu9HSOXhcViKnWLsBrgHhb0cCxu5RIzZtAl93Y9qeh4mBDVYjsV/LjupvCe/4qvpUrHtyqNksLiU4LZdpXZSMayCslgFuWNpOSJYgR0LU0zLdmSYxoSXqAkfTZqwEzS5+T1mwv1PGVX9O1wKw75KaQRZfAp7vjJsBGL08hwxFoBixaAem5sUqJ7H8VZsihibp+S/ii1g+lfEZtDQnO5maI8tQyyo8UBOlifmE8osXzN2sX0b9qUYZ8+Xestb1YWp7ETLO+pomW7BynFZnu4C5buL2h0tgwHZiMXzjO0SLTtRgmyQAASC5C4nkdvdbVKW2PyNxdH6Ik5w707LucsWf1lQC4MFzD8oYvrvoZwJl12MdsZfw2ttXRNzdLT+qQ+t8CVYWrCOxYa2Cxp1tGAvQ2y8dQpexaaJ0IDSlWai9/eUYZBCfDjcISXhxL4DbmCZtsjzxXYBpRXbi1kexSyP7Z2TIA1P9EMx+rHyPqS4sYNppfXWvlhPS6AJulhTdLGm2AlNwgNVl2XaLq7vQ9vF7SehFxmTLNEJIPOfxxKNcly7xTGguyDtxVmsYNm0YFvFqCdHBO/V9p85+OgfLAZdV/Y6N/obqHFIHstM9BfdjiUoqlMcdzTbMPab4ti4J/oReBPk2QRVyOnlxpNJnztRjLWQ5IkzaafXVFPa2tiIYGd/6A/UGNBgojfkFGrljmBSUJuiJ3aL3TPtFqecjd4u3R2dAN1mczu431vs8YHAVesY2ULHx7FpnmiXCJYHnZ07umMTMUTHzPfdlh2OB7aImxL0N1KMvuApOuR4YKt9q8fhOlTW+gHpwMAZbFRZ3EU7HD9eD6nPabvyMPEPfyTmNY0UJ3pGHHtGjH4iNr8PZr5VThejY0HBRdCqHiZj8l1QhmM2MbFLdlA2C6mHU/JQrLL+Ygxgu9hOViPEtmvBq4h24vrRx4wRm89Y3ZBH9BvHHb/FST/tj8XW5zGqVYxaxHYrjToDou2F/OyyU4zdDMQqSHaGnU4XttjxDpggliG6LbLZHT3W+SOSj6et0R7fQLm6NqmpX0BUdMKx1R69J6cAsojRoLNXzN52TSLqbH3+9iKx7a85eQAq/b5IJDovq81V9V8WywW3IF/qTpTZI6Pc6Iy4Ko381AM+YONn2CORhTE3lK2s6MvIbqjNLvfY4+7mj7pE7E3K2uReTg+qGhoGVnomdCBgZsotn6G5KeClPdGwfU5bWocYLXVib5atGjf6wTywRzSdQjlbxKIMFfVF8aI7Go+pNZ+G3uYm8EXHYYQQ3/wdFOK4byH6ElUpX0Kq8VJEzjmd5QkunT9hOgsT6Is+o+7oEPQCyhiEa7/uhpX9nwOyCDKM/xKqvacu9uoM6koKPsWu+KicQypqhL6iHK2lhPG40vdTjc9ZDSTpm77V6biju9DF5GF1imJsjBgrtqNlF4pFOx0tDotA5qdYCbsvJr7THVtkd09b5JSH4VgURqpDxeZtdnd0kZ3USS0Z/5bBiCW6z6O2751q+467LTt17Xuvp+iY2r6Pgawlz5AGfgnfwHeuXDlH7fxfQbOM7oAcsCSesafc0f3urWegIPvE5o4uj6UDC5WF2u1LvOEZ5TbQxty2Gz63o4XacYjz9gmoFjDGvLLoJe7oUvvctrQj7ugsp9i80y4WBXIKHa29IevOgVB3ykisyNVAxh/JoNU2xg3tJ3ab3d18W5YQOR+dqh1V1IrJQrXdCmFZ9PPO/p7YlaOxhecfxUEMjEdE5d9HUW9Z3NPI6KE02lEWnKAjI7I26yn6xgMRYdi3GNTpbpsNDlQRtyoQt9wibvqaqmu6OOoV+TwY9uyEHu2zlee529K2Q12u7AN9UFSJ30580cyXIPn9YvOHX4ttS78Wt3ZaXflbxMR2uTfkKjZ/ZJGHOJwuweEsc5Y4Btjg31xnycY00uZOW0NXzW1bvT1vTltgZ55n7C7oH4B5HzB3OAbM3ucYML8D6BNAC0CfcAxwiM3txaDaYvS2kdfEohdg5Eo61VPi2G1gPmAmH4ML3kbLZEPDShdBz1PAvVrki9DJypliLM8dLdgjJrYSd9kT1XwqLTTV3ebZk6X645hTjF6jiLFyqKdrTkCINPiw8iwxOkBs3poN8bI9RV2RN7Cbj57wxApy5NFiQsyKgI3u9EQPumNX5tAxyCPH6Jjr58fQEg8+jbadjyNmx70jsGI2Hr7v1wPzpcaoK/9VV/7z0NvEYKBUC7+k/4Ux6mmxSInM9hS94Wh9HT0yKKX1QVI5/a4Xo7vdXyqi5QU06q3KdHHrqQtFyzbRv63XCw9Ni+NcpVaTnqdoX2QuJBGZCtGHsehtadepk8itXRfiRNK/BeOLY6F/2yNuPT1dXPtPAlj2uBPbOiv49HZjYxYi17kTWzuv+I6JiomdYqLdUwRjlncd99ixQfUhcyyikOfwoYcy8Sj21el7pmZDJRVDDa3f510mkCHgLrC3NbcUCnL63aWlnRdge5hJuG3AmbeZzdMS+xybT9C0Th7HimlX/ngMveYH8mh3wpPjRLdJq65/yZrVOXYhkq68eBQb6kfK60foFGaxciPMXqAJrN2Bs93rS24oWVKytERasp3vGxwtq6D0Jv1DvMai7ZEcLYEeuK9N4ZZ64J6Twr2gB+6rUrhdPXDnpXAX9sB9cQr3uB64B6dwj+iBuzfcK2FzXxg83p0emZwtlNw1c0JWvA66Tq7//ftnXP87ASox/pvPNAw3fMIxZCLDnE80DC08w9FOYAhpGSZ+zjG8iAzZ2jLc0MUx/B4Z5nRpGGp4hruRYYGWYegpjsGPDPZTGoaGExyDiAw3nKAmfnoEuk86riCT3fgIK0HozBe6lmHQtWRB36TOnOJxOnN6P05NXlSGwKQ4vovMAzCBdyy6JMnErh1rEAYfjtZn8Uo/AGl5JKWGIz3U8DKSB8wFn8NKVkZ3kr4c5yA4wCVzUxgKxRoV6CkGiW3PEFi5mhSZEpub5xULT+HCr9KudMMirpMoo49o5jwriMjb0Zm0bsYpUozmk38wftCmil2jKkBdrnC0XIMQmXvOtqZMZR0tR2x6kbfZzEX+A9xTroSixvNOo9MBz0czJvqkGdNiaXMZnaHPJWQ1z2UJXicH/v2TRnNenPZVnR+ptT7qAoGsIC0lQ4/FOunk6ec8y+jO7FGFmthtmFnz6pwsQb4Rx5VZ0I/aIxK9jAnfW35TML8Y5KP0+4guKJBB1XIiWdX3KdmLH1HJ/vNDbjyG8jhxiJ0D8kGlbo8MY62t75pbSDfjY9HqP1S7GdtgjAe9kDKW1AxUP7FV5PoIuON77dhCwJj5e8eVPXiv2s4shsA4jv0rwEme3yLPaRvGV40smXYM7711hq2XGDDciAyzz1Dv8quhmFG78tOhnFU57nsADV9VySaQKb7Gpi3RceWij8jioaPlNMxzcHbjaP0Er3QznJZBKY3o4x7M+w1rd+uFOSXvMPSrbGTRQlPx9ZqKn21W8ZONKv61w7QGf/8Bt0RJHvkYcf/mME6Z03I2lMOUCTwTLu1tJp6uLzHQceBSIxNQkMeJ/cB4p+2ZNLyO/TVtHwTNey3KMlBs52jqI3oTH3FcufIwdXUkWvQYjMCUXxymfcNG4jmeyXkMs6n8UOMAIx+gf92F9dE60kJViHwwNYxP63Y/6UfHw+grqpaq/8nxbDAWvYcUDtWN2ThhkIVJCBbh+2vE/0Y0SzNoJFX3TM4JlCXrQyoz1q7S+QEdsNlA6uK/WYibPiOobvpzwcBN/0PQW9gfBHMLWy90q8cdzcASPaZ2Se2z2FrgLGMLc7RkpfSCx3rI603B2FnX/pNOH68+BE3r6VPGNlbyT2qRFwBTcctRnM9+pHyNMWFQ3QTDXkfLRlw6hKEvaOYPVjLZyPneqmvbIVoRD71PG0QTaRCzTLqfBw+R0X3bOI19/Wzc/6F9DThkYl8b/8nZV+yQZv3kyvfJailMCGBqX0ZWUFzJZdHncEavuP/JnsaQ9cAy0hH080Tzkg+dALRDFLba4mJLvIob2xzxkB1oU8RD7idTQp2H3JRiv/eZ21Tnrawt3yrQ4d6p97ieoe195pRxkYBm+aevDZzy7636LNf24JQDJpX+SAc145XvUW+4D7zh5kb489Q6T7GAxvMrol62htrdB33YQXvxxv+lXjyjgzadd9+ltttIe/Ebcur+lzL86Xus/2cZ1qkZ4jMOHDZAhiOSI/TfsuJNZ9zkySZ7ZkfGUXnd46i873McdexdOo7KU3a8Q0duMOkWMZtCkuNV9FKXo1uT48VmOQ6gw50rOozdWYjlXaiI79Aru5LZwYZG+UfjA03c4BXvUiMbCLHih75KJDTrIZrn1/Ze6NK/EKNX5pSsudUuOFreTMP2dqtzcx1MJvJf3YQr9IodS9LclXC0TE3XPC2c8I76AGeo6SOlrSJ56mh35Sc6e9euc69tF/A5trqGebu7La2XeFXChmlC5iUOz5dkMTfmxHGhU+mLwrducbTcIWjy/svb6hTmWbIsOgbX59pkGL21PZijwBRBqXon9UmjGH2HlCcGo8hjigOtEPzYZWSJPSdlDtf6Ihtl7DoIaiTrt7RshcoHkDiUqrWIjL/ScjyxPDJBq1MgwadJVo557zQ3dQlNfbE2Wt4lXgWneHaxzXNh4u7hdk6awwfVh1BslXecY/NrZEUIssen8CdQopFvkzcANI+i3NEjZdHjXFIPHdQpZnMHffSKiunCZMS3DRVDFoNi1yr4CL+srUFxT1ukRBz4CP4fbxNhH9zeaSVPNeUsorCB7OngTpgsgZL+/S26uNSL9LDy+S0Hy6LfdI6v1a/vabpcYInMQM/nhdgtB/FxqN3Rsh8fBbxLn690JV/MqCNGc6LEsTUDusw0MN4YDTqv1bS4Wr7FETYadFZq2JaZsc0riWW0iYmSaCYIfd8o8vziOLYvfJtNeQsKGu+X0CxHTGNPPQjDJmQYq2X4+zccw3pk+A15eAvKWLsDmyG3sAbjUrLAsE9QFxh2CUYLDNNT+qTzdX0SJ1RcIE9Nd3XeCn/U7q/zpm7iPWUtq7/rSf1FKvVV5Wj5NGUwt9tinuNfLCTHZPqj3mISx7LQyfuJk/eeQ6/C15HeXRPFTn+T9hNDDrCc2umaLbS/1yFzurTywpu0fbTb1MlIdpo6GbntLTryIchcXE/BF9eU2W/S2huTRmcUWRAq1rc0M4qLD5AXA8paE47W69mkDPnA78VX4ntCJIOylMzvSlczt7DMCXITZj6ElPcAzXxdOs18DYRK65uazB/9R3fms1nmyIeZe1MHI0RZAw/QBZCP94M11qTO2wjT0X/QQe1OZJoOTJ1YpfFqWrUwgH0xmw5gUWMwgH0ju3sASyB8iJ7WPYBtTNOv5jyRMpj7sWBqU50RmusiliuqCnKVuFwJBLmiutRcD6Trhs23a4zsR2a5zTZSyVv76bAZxVKHzcvQINYeoPXXhEQlKK7zaqP4D7H4WEA1/m6s0xIWHz8DUQb9g5ry5Sws+Aft1fsR06am5Y72woTwks7GtC9JGczG/pSi7NYelB1WzYhlhJdnmdGLKZ7i1z14ijaLsYkG3yCTpLoRGhv7txHnZmP/kks58rpJbf9kP1fbtW9oJklDXv/WSVLOfsNJUiE+iIVJ0myzSZIYLcWHtY6WGjKVnQ+9w3VkJqt9Za3lqpTO4bweOoczkEt8rUktxF8jtXBouKbNdQ4/xzb3r9RC7Wsmbab/G1yb6XhNUwv3v/qttfDw6/9iLfSzqLVgtRjUwuGU9va0eXuLPyowr6pOVee/wk1VD72K3TPkeRhfiCR5HsQrfZ6/S8lzTQ9tvMFI3V++gs4moby8D9VuE66BaeqW+cVC5+VG3M8z7n+n3NpJLfqu3a8ady7rWMQ6iBh3nCbv15YsqhCbj2S5o2fcsaXZOE4YR8YJo1PeBPgdexv1sn04mZ5F39mILc3qKc7PWZyTL5M4WSyOs6c4LSzONhqHDrpjIzDKRSTK8OQ8NfEKddY/fzn5gpDYvCPr+pKlmqel8sLu2vDkpMXgX6d2zngNz9APGPp1ujQM83iGQcAwqHMGN9z8AJer2wpylPGo2v1nNGPR0+SmDNNJB949or07IEHvOpVPQIq4NUEmkAbzx3Koo7LY1cQkydpgYn6Wo/Vhop2R7ljQLhZ1yitKnkFFdhZqSn9eqvxcs7+UlDwMuXcOX+eJjcPXfC4ir/kMV1/z8RR9FPkDLqqP30stlGh6O2T5TuQlyB4rx07eV91LTSx9L18jdm60XVurmx8vwpnxGjLAOUOmdFlosPjFSfIF6EuhbGLRLwko94MRPLJDLS/ZLrbdkGMnwznkmwD63TwKR3JjGfLNXrq4RIbAaDlkaQpXu1en2WNy2hhc525C0bOQfele+ngEZHkXl7Y3A72rJWclZHcpxaFoSOH2K4LyyF51kHt4L1nfZhPiK3OUypfp8jCoFocRP30JZu5HN+NXl0/h1hSIjXqZjk1j6V8OzlZXwPvbhqh+3pNmx8UXJ/XwM3MWn617X20h/gaDFPfehGuMP36Jrus4qW/Hh3EFL1PJlyl99tJGNZAWr3MJKePZL9x+a+69XyLrxY4Wa4KOsXYDEP/iDPFHFWL0dHK0fotd+Zq84//e9fGfvGR4/216X5FfYnyxPdiAkval5/9vxj9T5b++Z/7VjH+Qyj8O+ZPs68qVh+COEnkRSzdTEKC5RhMli9zRkyUL3dE3Sio9baMbndnCQrFtfBOEFZ6xh2FOv/UbG36ZpSx5ga6IjEi+7xL92BM9ORPSSAx6G5qYBVp15GPShpaojWg7V97PtrNvvNgnXfjd8oQa34oJYbnG3yBk9xH4bQKuuCIcqYZLHYif8gcbgIp45eyGSCCQ3RCUs1dUBfw1gr+BhNkBv+wLVQWya4Oh7ECwYfmYsdkr/XJdNn4Bn52fd8WlgnvC/OxgIzDhp+/Z8D/54rwmu9Yf8AmhccIsCLNHIUsDSQU3GYHshdJgJFDTcKnM7iBX9/dr8/InSrM982eUeCRpnpRf2LhKrgs2+L2T8Vv+cH7eoqpAxOfCnR5cZ8M/qUKuaqjB7RZYlJ75i1zqp/yusyvPpBmgDj6Sk33vnDe/WPMddfK7T3ZfYPeXzS82vL9vHsXXmNzfwO5v0N3vubxT3fM53Z2FfFNcDSv8oWBDva9B1sXUlsdZblwe9X4Hw8vLiw33X1P1gGMa8jkNC/X7/SS/Dy3X8nd8C/8WXfrOMi2/ZZht2mr2TbWyK5HYjd+aQmNtglH9LyDEp3R3gSvAbz7Ej6ERo2c7CTiEd3UlEvhBQ91X4BQhbIKhFn6Tgd/x4JLxbvw4B990h3AZhIXgY9ZB+BiEB9jH7IPU/Q5vXiBYmpyWYf162ddZejkHse+Sv3o+keC/pzXmp98AI38WyLAO++1M56zMrDmOvivta4TpQ6ddNinnIn6fRdvN5R6SQi8bbkFkU9MpYN8TN4LsfxkhCGn9KouFkkznjMysGZnZMzLHzMjMK8ksnJ15Iq251z0Zben3pt1nu9NK4t2Ajy+VROJX/SDeMwuN423J1MQblCyPVp7hrKziF4nEg9gJz8h0lmRmzczMa7bda6XlxH0RdkNdvEI26krJqySzWJMV+aFsaZBe45eJRH/cqeHBRWo5SzKzZ2dusDWn3QvcWK5f4nfNULcXsvSbrVT/f0W7BXy0DsdPVpoM8A/Q3gzwr1Ff7YnEKIar+0R+AOXbAPw+gcp9n9WVmXWvzZWZ3ZbmyhxzT7qYmXdnhphZ2NyrLLM4gJKCvGOI7KABkMVO0r8cbRDSseraRML2X81r1gi2DbZx7Cv95fjnRkbchn+Ose/rvVgJXgv9+P8hvIP7WeBntIcHsu378Jvb40jsZHd+hLzHrDS1zfgnz0aJt/DPShuNcxoIy6NsHyx8TcXyKWO7HD+b7ZUmCPerW0GsT6dN9FcDgG0TI36DX+s+m0E3dOhCYkpvmtoxJMp603wk/KjYCWPMByD8O975NRDLVW307kt3eBiM3xbXQLpLVRG2AbFd3VyidSD9QJt8Ajz/PJopYauEP8dVttIhtAR34BrjLUPoJh0fIfEM/KlS2S4cRreJ+At+0HvNcBZnBFN4uVWzG2rC9tpawbaPEG+pxX6L1VYQ35HGtzZQhv/A9GVGfIPEf1no/glWZPvMQuM4kMAvG+1qeZxsm7ViHMpflE6/yZ+DxLx0bgMPdVfJGXjnEca2BYk9QPxdTe2O3lS6ofjH3pcSG1C/A+FPzJK0w32CbR7Z1VTNAC/wIWkCia38XhSvsQ03HsbY77FdFf7DwngzLcIPvx9+P/x++P3w++H3/8+vcTibz7B93MuHa+dBFpNwf7qW7tDR3zBa3ZuqYwhNV92TagebR12g7r/E9hFX91hS95xS92hS2H11/qHuqfXFmUSQDPCsxcl9wcj+Or2Lk/ui0QkCpdW9tbayG+qeWuoeUefr9GPr3oiL7UfH9j1K186n1L2/1D2oNgws1uDrBxRrym1niuqty/9MgsrT5aT8CUar5TjB6Budxf+ndpLcx173G5xFy3EJC6ewcBYLF7GwloUrWHgnC3/GwkdZ+CQLd7FwPws/ZOFJFmaw+fdgFl7CwiksnMXCRSysZeEKFt7Jwp+x8FEWPsnCXSzcz8IPWXiShRls393BLLyEhVNYOIuFi1hYy8IVLLyThT9j4aMsfJKFu1i4n4UfsvAkCzNYex3MwktYOIWFs1i4iIW1LFzBwjuHGdvP7NLSK7LHLKyONMiR7ILcwtyC8RMjhMq/Lb8gN68gt2AsxQXG5A1UNSzPXuELhXE5b1Lu5Ny88QU0ysTb5FAkLK+amD1GrloenrDA5XGVVLikSZPzJtTiNppjs8fgumANrgJ6PIvKaPSxgpAbXlUvV1VDKIdoWKde+RtkX6hRyG0Iyr7ckhnu8ZA0o5Y3RHKrI/5AzXh/jUCouqpwnZBbs6oB0qOhHKJ3WIE1hAT3Qr5AFTKyq8aAjFn64a/sa4K/UG4/3AvWVMlVQq6vTqoNVdX7pLqaUDcFiXq9bAtTSSbbJZM0pKpQqGoVTUO9vtEbIgWrqvd7IV5QJn9ovjSP6nBYyPUG63Et7V9ux8OYj1b9WPd5GoLGv+r9v/q7WNDupdh9XgXbb07Hn6aj83XxZRZf5tZXeoqP6xsnwQeq8VW/v54BNQxP1/UTyXVL5vOtun5BdbCPsX4hg8lu1/nnRYzVqutnHuut7VfM9LeU+XQ1vurHb2Qd3r268uuODRFuYn2ESqv9RBeLv0HoLr/NQP6bmU6tun5p/QBtv6TXnyp/iy6+2s9tGKjtF9NZ36+Pf6/QfcYKPy7oGKLt783qP6qLL7D+QM1gnU23zqwLH9TFV8c969jAY+JE4/jq7yFdfHUcs6NM25+blX+Drv3tY/H3sfiiref8H9PF7z73hdKrvyX/J3Xx17P4668RNO1QMGk/W3TxcXmXhpR+29pz/q+ytXKbbtynniujl1efP7586uDiq+NCZYkxv57+mJU/OZ5i8U+cZfzjXNvix0XquT+qYjJ08VW5unT5q/v3dkk956+G3+jiq+NSgQUHLD3Hz7Bo4x9g+0EeqDo7/fdji4PJ/Nk+wAqLb9fZr74/GMDyz9Phavw7TfofNRwgaPfrVX8N1cx/WHr2v7zt8j/xJnbBNsHFpdS5Bv6rt0n+4s00PObsOf+efjbgVvtjLW5N9rNa3JbsP7V4WrJf1OLp3f2dBs9I9mNavJfhPMMGWukyxHsn+xMt3ifZT2jxvkn/r8X7dft1Dd4/6a+1eGbSD2txR9K/anFn0m9q8QFJf6jFByb9nBY/L+m/tPigpF/S4ucn/Y0WH2w4v7LBbFL1D1o8q7vda/ALku1Zi3efi6LFh6VgFuKzP0nocbpHbaoeXAzHx3X871qG4+Mx/ucn7a+7HtU9jNeSvIcK6brzVR5n/OpzV3VP4vcZrj7vVfHzLSx9hqt7MLsZLogUf5BlEGZ4hy6dDQzf4Kb4Kwz/nOHLplH8V2yB4xdWiq+Zw9Y5mJPZYaVypenkeo3gjuTzZdW/2GwUX6bDpzB8gw73M1x9Pq7ijzC8UYfvYfgaXTpfqemz9wPUPZXHplFcfS9B3SP5Boar7xuo+H0MV5/rq8OpnQxXn+ere0J/wnD1vQb1WfXIdIqfKNfyz2f4Oh1+B8O36PA/phvb8ybCn9oed6Uze9D5mYMMd+rWx44xXL9ulpZB692iq/fzCJ7qH/DcJEynUZfOLMKf6mfM5PIR/gGCXddOwxnG8gom7f12wp/qZ35KBjbnpZT/UYbry7mJpJPq37Zl4Ngg1V+9ZHZelgme1Qvx/sIW5h/Uvn0Mw5/Q1eOEXsbnRDX0Mk7/Jyb4072Mzxl7wQR/1ySdT01wh90YLyZ4an83y4T/JhP8dhP8ARP8CRP8HRP8jAme1dvknDQTPAD4Rdb+QjGTV12vbe5tfO7WLpN03uxtfB7Xmd7G9YWPngdw4wd1HjO2j8m5iCb4dSb4j03w/9fHuDx/64Nj89T2ss0knWN9jM89O6+vMf+VfY3PJavua3w+WyvyWy8QFF157jdJ/4m+xueb7TbhP8zS79Cl/6kJf0Y/2t7LWX351PXpfsb8YRP8rn7G5849asK/ux/yDE3Rw+sm/Mf7GZ9fl9PfmH+mCe43we82wX/f39iutvQ3PgfvQ5N0TpngpZnG+EITvD6T6s3u0+otZML/dxN8T6bx+XjpDmP+cQ7j8/2uM+FvctB2p6/f2x3G5+9tMEnnpAne22mMjzbBrzLBr3can08YMeG/1wR/wgTfYYL/00nb3QY2bvkLO9xEIbjB/G5CKBiUJzSuqpK9wRpfaEJjKFgd8NWHJ4Qj9X7yuGBiXn7RBNcEPGUq19vYSA6Z4tfS81KQ/BRkspB8OzUcqZbcUjI16TqzV1fz8yUJnx7I/gZJ8hTMCzbQI97O+s3imXn0DK9zefX3O8WZeBZxCvAF6bPiVF/u/baiRGR/AOQN11WFfDVSyFfrrpCnrPB55WDIPa8iT6KpkSPuKqrcFZMll8ulFmDu2eicFHlqbaQBkyzE174D/gafN+Ces6A7fcLkwqQrvYFwqIeUXMkkwo3ICiWrcU2tDYZWVoVq3JWSq7aRFLFxfkWR1FMhuwXzrgiwMyA9hZLkD5IHQ3ie4Lm8fn4W/PrXw88miu6N9bOIYvCS9rfH6n4V/Nt5i7QiVJyjlirOXUsV566liu+kpYpz0FLFOWlp0TlqadG5a2nR2RbeG5LDcqS2NtcrSNKc0gWSx11RKUlC92mxklwvefFU2LBgAElSTVBaHghWVwWkGmjUYakq0iR4g/WNAZ/sq8mdUlQ40ZhJ6n5GKoHiQ6sE+py1JlJfvwqicJTU/WiVsUrSrAUlZS7JNW8mnnlLSs6umdTzZ82qcFVKlSUzPC7k0CRRowXIoYeCNPNH80rK3KUCPpRVMf1BnMXF/FGGPR9cquOlByx6wxEiuZDM4RzP8NSXwPB425RiGh7Aq+HKLTqro4TJcZWpyXOHYhqoqIczfrVlyM8XmHaMD9bUpk2PsGQYO5GSnIuphVKOttTd7vEkU700KWeC6mu5+9zN1GxMzt9NrVLTs3JTcsN3M6DOAwEpebLwdztJWJsyOUzUQIDUk4Z1JerxqOn5EvkYTYqEfTWpJwzrShDy+VIK0NM5wNro9BxUXQI9nHWtb/Smx1kbmXfKQa+GbsLotGqDlmRwFq2ey+B4Y71hgHiqR0w53DnV3siZwKkwd1q1Pv2acFCqg54WlEcPoTVsc+jt2BDqezxVW++32Bm2emvRngqtly71PGW9iNXhMGcRySPFUyrjrM4ZLi7mzspNPR3Z0IukHJWcmoj2OGmjVLRntWtTMDzh3eRgdJ3rJUcKGziI73ZAuK7p+4K1enNKHqOulYD05d/tkG5dnuQb1RQTOuszsg26ZYOD682au8n540b1yR1grlMFeZnM6OTxVLP5Hk7YNugYDaRLHm+vu6c51hrusWOm9afWp2pVPYDcYIRDjxA3KIT+fPVUU25c1V3z+QWpx3Trxx3+BoH6tf8BTt6pODaLAAA='
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

def solve(A, N):
    MOD = 1000000007
    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
        elif A[i] == z:
            z += 1
        else:
            return 0
    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: Accepted

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

mod=10**9+7
ans=1
cs=[0]*3
for a in A:
  c=cs.count(a)
  if c==0:
    print(0)
    exit()
  ans=(ans*c)%mod
  i=cs.index(a)
  cs[i]+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
i8 = np.int64
i4 = np.int32

def solve(A, N):
    MOD = 1000000007
    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
        elif A[i] == z:
            z += 1
        else:
            return 0
    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))

main2()

Submission status: Accepted

Solution code:
import sys
from bisect import *
import math

input = sys.stdin.readline

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

cnum = A.count(0)
amax = max(A)

numind = [[] for i in range(amax+1)]
for i,ai in enumerate(A):
	numind[ai].append(i)

if cnum==0 or cnum>3:
	res = 0
else:
	res = 1
	for i in range(amax):
		if len(numind[i+1])==0 or len(numind[i+1])>3:
			res = 0
			break
		for order, j in enumerate(numind[i+1]):
			res = (res * (bisect(numind[i],j)-order)) % mod

	res = (res*math.factorial(3)//math.factorial(3-cnum)) % mod

print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
MOD = 1000000007
ans = 1
cnt = [3 if i == 0 else 0 for i in range(N + 1)]

for a in A:
    ans = ans * cnt[a] % MOD
    if ans == 0:
        break
    cnt[a] -= 1
    if cnt[a] < 0:
        cnt[N + 10] = 0
    cnt[a + 1] += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())

T = 1
xyz = [0]*3
for Ai in A:
  if xyz.count(Ai)>0:
    T = (T * xyz.count(Ai))%1000000007
    xyz[xyz.index(Ai)] += 1
  else:
    T = 0
    break
print(T)

Submission status: Accepted

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

    t = [0,0,0]

    total = 1
    for i in range(n):
        count = 0
        for j in range(3):
            if t[j] == a[i]:
                count +=1
        for j in range(3):
            if t[j] == a[i]:
                t[j] += 1
                break
        if count == 0:
            return 0
        total *= count
    return total%1000000007

if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

arr = [0,0,0]
ans = 1
MOD = 1000000007

for i in range(len(List)):
  a = List[i]
  
  b = arr.count(a)
  
  if b > 0:
    j = arr.index(a)
    arr[j] = a + 1
    
    ans = ans * b
    
  else:
    ans = 0
    break
    
print(ans%MOD)

Submission status: Accepted

Solution code:
n = int(input())

visited = [False for i in range(n)]

lst = list(map(int,input().split()))
mod = 1000000007
occur = [0]*(n+1)
occur[-1] = 3
count = 1
for i in range(n):
    count = count * occur[lst[i]-1] % mod
    occur[lst[i]-1] -= 1
    occur[lst[i]] += 1

print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007
l = [0] * 3
ans = 1

for a in A:
    # print(l)
    ans *= l.count(a)
    for i in range(3):
        if l[i] == a:
            l[i] += 1
            break

print(ans% mod)

# print(l)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

C = [3] + [0] * N

ans = 1
for a in A:
    ans = ans * C[a] % mod
    C[a] -= 1
    C[a + 1] += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
MOD = 1000000007
ans = 1
cnt = [3 if i == 0 else 0 for i in range(N + 1)]

for a in A:
    ans = ans * cnt[a] % MOD

    cnt[a] -= 1
    cnt[a+1] += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
counts = [0 for x in range(N)]
ans = 1
for i in range(N):
	if A[i] == 0:
		ans = (ans * (3 - counts[0])) % 1000000007
		counts[0] += 1
	else:
		ans = (ans * (counts[A[i] - 1] - counts[A[i]])) % 1000000007
		counts[A[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n = int(input())
    aa = LI()
    cnt = [0] * 100005
    check = [0] * 100005
    zero = 0
    ans = 1
    for a in aa:
        if a == 0:
            zero += 1
        else:
            if cnt[a - 1] == 0:
                print(0)
                exit()
            ans *= cnt[a - 1]
            ans %= md
            cnt[a - 1] -= 1
        cnt[a] += 1
        check[a] += 1
        if check[a] > 3:
            print(0)
            exit()
    if zero == 1:
        ans *= 3
    else:
        ans *= 6
    if sum(cnt) == zero:
        print(ans % md)
    else:
        print(0)

main()

Submission status: Accepted

Solution code:
N=int(input())
A = list(map(int,input().split()))
lis = [0]*200000
ans=1
num_zero=0
mod = 1000000007
for i in A:
  lis[i]+=1
  if i!=0:
    ans*=lis[i-1]
    lis[i-1]-=1
    ans%=mod
    if lis[i-1]<0:
      ans=0
      break
    
  else:
    num_zero+=1

if (num_zero==2)or(num_zero==3):
  mul = 6
  
elif num_zero==1:
  mul = 3

else:
  mul = 0
  
print((ans*mul)%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    if A[0] != 0:
        print(0)
        return 

    ## 一番多い色の帽子の数
    color = [1,0,0]
    answer = 3

    for i in range(1,N):
        if A[i] not in color:
            print(0)
            return 
        
        count = color.count(A[i])
        answer *= count

        for j in range(len(color)):
            if color[j] == A[i]:
                color[j]+=1
                break

    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD = 1000000007

memo = [0] * 3
answer = 1
for i in range(N):
    first = True
    count = 0
    for j in range(3):
        if memo[j] == A[i]:
            if first == True:
                first = False
                memo[j] += 1
            count += 1
    if count == 0:
        print(0)
        exit()
    elif count == 3:
        answer *= 3
    elif count == 2:
        answer *= 2

print(answer % MOD)

Submission status: Accepted

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

c = [-1, -1 ,-1]

sum = 1
tmp = 0
for a in A:
    sum = sum * c.count(a-1) % 1000000007
    if a-1 == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif a-1 == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif a-1 == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
print(sum)

Submission status: Accepted

Solution code:
def main():
    import sys
    N=int(input())
    MOD=1000000007
    
    a=list(map(int,input().split()))
    c=[3]+[0]*N
    ans=1
    for i in range(N):
        p=a[i]
        ans=ans*c[p]%MOD
        c[p]-=1
        c[p+1]+=1

    print(ans)


 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

c = [-1, -1 ,-1]

sum = 1
tmp = 0
for i in range(N):
    sum = sum * c.count(A[i]-1) % 1000000007
    if (A[i]-1) == c[0]:
        c[0] += 1
        tmp = c.count(c[0] - 1) + 1
    elif (A[i]-1) == c[1]:
        c[1] += 1
        tmp = c.count(c[1]-1) + 1
    elif (A[i]-1) == c[2]:
        c[2] += 1
        tmp = c.count(c[2] - 1) + 1
print(sum)

Submission status: Accepted

Solution code:
n = int(input())

hats = [0, 0, 0]
count = 1
mod = 1000000007

for a in map(int, input().split()):
  count *= hats.count(a)
  count %= mod
  try:
    hats[hats.index(a)] += 1
  except ValueError:
    count = 0
    break
  
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N=input()
A=map(int, sys.stdin.readline().split())

S=defaultdict(lambda: 0) 
S[0]=3  #初期化

mod=10**9+7
ans=1
for x in A:
    ans*=S[x]
    ans%=mod
    S[x+1]+=1
    S[x]-=1

print ans%mod

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MOD=1000000007

# cnt[x]: 赤、青、緑の中で、帽子の人数がAi人の色の数(0<=cnt[x]<=3)
# A[0]=0（最初の人は前に人がいないため）ので、cnt[0] = 3
cnt = [0] * (N + 1)
cnt[0] = 3

cmb = 1
for Ai in A:
  # i-1番目までの組み合わせ(cmb) * i番目の人がかぶれる色の数(cnt[Ai])
  # i番目の人がかぶれる色の数 = i番目の前までに同じ色の人がAi人いる色の数
  cmb = (cmb * cnt[Ai]) % MOD
  
  # 今回1つ選択したことで、何らかの色の帽子をかぶっている人がAi+1人になった。
  # となれば、赤、青、緑の中で、使用人数がAi人の色の数は1減ったはず
  cnt[Ai] -= 1
  # また、赤、青、緑の中で、使用人数がAi+1人の色の数が1増えたはず
  cnt[Ai+1] += 1

print(cmb)

Submission status: Accepted

Solution code:
N = int(input()) 
a = list(map(int, input().split()))
b = [-1, -1, -1]
x=1
for i in range(N):
  x = x*b.count(a[i]-1) % 1000000007
  if b[0]==(a[i]-1):
    b[0]+=1
  elif b[1]==(a[i]-1):
    b[1]+=1
  else:
    b[2]+=1
print(x)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

ct=[0,0,0]
ans=1
for i in range(n):
  f=0
  ct2=0
  for j in range(3):
    if a[i]==ct[j]:
      if ct2==0:
        ct[j]+=1
      ct2+=1
  ans*=ct2
  ans%=mod
print(ans%mod)

Submission status: Accepted

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

dif_colors = [0]*3
patterns = []

for i in range(N):
    cnt = 0
    tmp_color = -1
    for j in range(3):
        if dif_colors[j] == A[i]:
            cnt += 1
            tmp_color = j
    dif_colors[tmp_color] += 1
    patterns.append(cnt)

ans = 1
for pattern in patterns:
    ans *= pattern
    ans %= 1000000007

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
*A, = map(int, input().split())
hats = [0] * 3
ans = 1
for a in A:
    ans = (ans * hats.count(a)) % MOD
    for i in range(3):
        if hats[i] == a:
            hats[i] += 1
            break
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
ans = 1
mod = 1000000007
cnt = 0
maxA = max(A)
dp = [0] * (max(A) + 1)
for i in A:
    if i == 0:
        dp[0] += 1
        cnt += 1
    else:
        if dp[i-1] <= 0:
            print(0)
            sys.exit()
        else:
            ans *= dp[i-1]
            ans %= mod
            dp[i-1] -= 1
            dp[i] += 1
if cnt == 1 and sum(dp) == 1:
    print((ans * 3)%mod)
elif cnt ==2 and sum(dp) == 2:
    print((ans * 6)%mod)
elif cnt == 3 and sum(dp) == 3:
    print((ans * 6)%mod)
else:
    print(0)

Submission status: Accepted

Solution code:
n=int(input())

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

cnt=[-1,-1,-1]

result=1

for item in s:

    temp=item-1
    if temp in cnt:
        result=result*cnt.count(temp)
        cnt[cnt.index(temp)]=cnt[cnt.index(temp)]+1
    else:
        print(0)
        exit()

print(result%1000000007)

Submission status: Accepted

Solution code:
n=int(input())
a = [int(i) for i in input().split()]
mod = 10**9+7
ans = 3

red=1
gre=0
blu=0
for i in range(1,n):
    temp=0
    if a[i] == red:
        temp+=1
    if a[i] == gre:
        temp+=1        
    if a[i] == blu:
        temp+=1
    if temp!=0:
        ans*=temp
    
        ans=ans%mod
    if a[i]==red:
        red+=1
        continue
    if a[i]==gre:
        gre+=1
        continue
    if a[i]==blu:
        blu+=1
        continue
    else:
      ans=0
    
if a[0]!=0:
  ans=0
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
MOD = 1000000007
ans = 1
cnt = [3 if i == 0 else 0 for i in range(N + 1)]
 
for a in A:
    ans = ans * cnt[a] % MOD
    if ans == 0:
        break
    cnt[a] -= 1
    cnt[a+1] += 1
 
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

p = 1000000007

num = [0] * N + [3]  # num[-1] returns 3
tot = 1
for i in range(N):
    tot = tot * (num[A[i] - 1] - num[A[i]]) % p
    num[A[i]] += 1

print(tot)

Submission status: Accepted

Solution code:
MOD = 1000000007

n = int(input())
a = map(int, input().split())

res = 1
values = [0, 0, 0]
last = 0

for e in a:
    yo = 0
    for (i, v) in enumerate(values):
        if v == e:
            yo += 1
            last = i

    if yo == 0:
        res = 0
        break


    res = (res * yo) % MOD

    values[last] += 1

print(res)