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:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAEjV410C/+19e3wTVdr/JL0Qbk2KiBUQghYtIqWBAq3okgKBCaSlUEB2FaclTWk1bbrJBIqiom1dY6yi6yq7n73w2X1f1/X9ueu7F190d4GKUNf1gqIsiii6ghPLTVGs3PJ7nnPOpGcmMwVc3/evDTQnz3eec3me85znXGbmnLs8vjlWi0VQP1bhOwJSuSPdhHYz/D5/igWwEqE/fI8WRgrZQGdxfG7BrQl7WNJqaGN8GfCXCX8lVkqXWN2acCTjU0MLF2YJ/MetCf94g6AJBcGZiodl3bOconuWV2tCRybF1/fTxrOyeD0sXg/jV0PBKmhCVb5M9reY4YuZXGo4m/HN5vjxU3lArsXfexayci50a8K1jG+tLt5CiJctnP/HwcJFan4meilg5VdDtR4mBhtWTC2eGKydEGxoirZMaCmZOmFqcWEkVDiJlMnBeOdWLNHoMY+VeSizAbx+tXvz4M9O/Glo49jjvx0+8oqS2VMPZOO1UhYPq6S9yVGfOaa/tb+lWFgHSeO16+FvJvy9dPeAN3//3uS3B9y9XvqZ/6/bH2xMvnRfu3/YW1UbWx/4rvuzCZ9JN+c4VxUVeN72bf30yq1DNwya9fORzZvWeG991kw/A6CQQwzwXVZjfKLFGP+9YIw7Uham/Yw2wb/MMk7nVyb4303y/YMJf1O2MT7BBL/DBH/aRG8PmeTrM0mnxETPfzLBZ5ikM9lEnytN0nnIJJ3PTfg9JvwLTPL9oUm9ZJnYz2KTfJ834Z9sUp5qE/6oCf9Ik3ocY5LOKyb8H5jg+zOM8TtN9NNgos/vmpR/jYnerjXh/62JXD80KedKk3QOmZRfMkkn06Rd/MREby+blHOoSXmuMtFDj0n6X5iUs9ok/X+alH8IpDNGGC5sXEH7kWUM9zLc4ad4ntreGV5ZW63pn8qzKF5dq03HlUlxgaW/TvV7rDzHLnVryjOX6W3rcC3+fcg3F9JxB6q5Xl8QNmZSvJrhar/3joXmu26Flt/O9Lxel++qLJqO4Nem42fpuxnuYBcamVxba3VysXqpHKFNX4B+OCLX+sePx753qiBJKxtDTVJErgnLkiRI81ZJiwIrGyJyIDwrWBOJBCKC5F1cLtUGwgxeXD4rGGoKLK5ZEQzQa8ZXpGa5PhyoqZVuDayR/PBLRtDfUiPVhQMBKdDiDzTLDaEmQfpeRVWkGLJtdhVJmFNEDofWeBbNr6rx+j3kcqgULjQ0RQJh2Rv0eBZVhRZLeGF+lTzFL69pDgCjazLwrG6oDTQBZ4PsWQUMVbJrmiRBOUKrpRVQlJpgMORfRWNGXJPrGppqpbqGcESWQnWeyvn+xkaa3ZS6YDRSryYxlU/CXxORSQpwYXI42iQ3NIIw4XAoPNvFRQiBEIGaRrXQfkBd/vqasCSHaxrkCJQXpIAUVtREGvwqt3extLhI8lRNlSrnV02WgkxfJHOSciloubGhCVRJixCZ5UI9RUi5Fy+GBEt7E2xoWsmSNcid6JYqVy5pCEVAtkig2AuKY2IAPhWUVRMM9AI6gVnmqZKAAvlKQ6hRg8isdJCfoUam+IOBmrAHrkySvFAm+JOJ2YDok4rUWghFsbqkcE3TygBkqdbmVFKbYLOy1BTSVihensZVtu764qUVYHmg6paaFQ2rXGgyfrR9CS0LarAuhMVf7IXy81aLgE4jrMJWQINoAkuR/fWcdYMEVVKgsVleAy2mGZpcKFyzMuBhduyaQnVDK25FtM681iYDD1aJtLKlRWoOhCOhpppgAyS7qoipOVXM2ZNY3UVApeUSqPdWCVKsVdGpNc3NgaZaogpAaoOVq6DC5FLQENG1TNRzQaUjtVXsh1pKjwvGaBIXozWtbiSRp7HcOd2VguqoD/E0NmpMKmW8VFSif9LMgVfnZEKTm6Oyx89s+cJaCtgy1jYxywWgssZQbSDddNBIIw1G1pNycS6QhLXiIBM6TePAPC0cAMexCsQ1aqOzWJOcz9d18er6GllfsayBYsWi62+kXh9+rfRDjSDlEqQlTauxcSwKRKKNAbzop2x1IUhDANXIoaBQFwjVCXUrA3IEkSBcYMqWAy0NstAYaPQ3NpOgeY1Q5w+GIgGhkdQEgo2hVej+MW3W2TTWNDQJ2BUIc2fNkiYXFglzfd6Zs6RJha7i1M9JhVOEWcuWlc30Sq7CyRRetgy4iwtdLg1ZylN0Bon/MgT1dyb8ZZF/VvKLfgvsd1YqBv7OYNetMAe1sjULxLMZdza72o+FthSWnUqF/5cN/bhFyM7uncdVXrlmIM5UH81W58lW4Qp2vQj+Hn34sWxcHfgpw6LDG/pjKX6d4s8kYwN13LPrd7dm4Yz5D4y/pudxK86cNzM6dtc4K86gX2W0PO4RG0q8l6XXI9HxQ7Z+vYSNW7LY/Fn9rOPwmRy+kcNL+XT8vfhsfl7L4dfyqzQc7uFwdbyH+HR+vMnh13H4Vg6fw6cf6MX5EVI1h5dxeF41xftxYzIynuNwK4cXcHgGhxdxeCY/f+VwXv9uDu/H4SKH23j9cHh/Dl/G4QN4eTl8IIfXc/ggDm/m8MEc3sLhObydcLidw+/jcAeHr+fwXA7fwOH8/GEjh1/E4U9y+CwOf4bDL+bwTRw+jLcfDr+Ew1/i8DwO38nhwzl8D4d/h5/XcvgIDlc4fCSHH+Pwy/j5GYeP4ttdTS8+moNtHM7Pkx0cPoa3fw6/nLd/Dr+Ct38Oz+ftn8PH8vbP4Vfy9s/hM3j75/AC3v45fBxv/xx+NW//HD6et38Ov4a3fw6fwNs/hxfy9s/hE3n75/C5vP1zeBFv/xzu4u2fwyfx9s/hk3n75/Bi3v45fApv/xw+lbd/Dp/G2z+Hl/D11XrIJsaz/jTXKYjtW+UsxU/AF23btNPT5JRfAkty7H/At320G34hXY+XEvuT8Bn7E6TRBSd2EvoRpNH1JrYS+n6k0eUmniH0PUijq01sJPRtSKOLTawndBhp7PYS6wh9C9JY/EQzoVcgjS42UU3o7yGNrjVRSehFSKNLTbgJPQ9pdKWJIkLPRBpdaMJJ6GuRRteZcBB6EtLoMhMCoa9GGl1l4thZpC9H2kHkJ/RwpHOJ/IQegvQQIj+hByB9EZGf0FakhxL5CX1yDtAXE/kJ/TnSw4j8hP4U6UuI/IT+COk8Ij+h30X6UiI/od9EejiRn9AvIz2CyE/oF5AeSeQn9PNIX0bkJ/TvkR5F5Cf0U0iPJvKfQfqXSDuJ/IT+CdJjiPyEfgTpy4n8hL4f6SuI/IS+B+l8Ij+hb0N6LJGf0GGkryTyE/oWpK8i8hN6BdIFRH5Cfw/pcUR+Qi9C+moiP6HnIT2eyE/omUhfQ+Qn9LVITyDyE3oS0oVEfkJfjfREIv9pUv9IFxH5CT0caReRn9BDkJ5E5Cf0AKQnE/kJbUW6mMhP6JMeoKcQ+Qn9OdJTifyE/hTpaUR+oCu31MKISPkSfm7BtarNSD6/H1q5UgbFXbbNddgbe+NmMfaR2PrxscrF3q6tRRVuQezq3FqOQZdwmVtQDkL0L+yjYeC36ShEXSJOUCAQW3tyxNiB1dbl2zYRHwGO4YvlW/BScr99NFnK2qRw/J09GcAvxl4QOz+dIVp2im/0RCHy8zTymxBZjO2g8T9i8ddd/5QIxhPNXQIxlTtBwOU7sh4HyHJ8G/oXsfX6vDJgkEelijB0yZZjyyG32IHkzuWJ2yGKfbSQiNBwSdkNZUvLlpQtrhLvPoQ3HbZg09iMw0bFCVKKsW0e1wmxfa9cIHY8mo9l2DwbFRL7QMH6Ertm2dB5QUiGPd7Y+1wK75/CFLaL7Yfl6zH6fXglQKIfVR4m0T0kmtg1O58sbYqxYH49oDb0gACSvrB7eO91+EG85zOWGFx1HfbF5Pzm8vYTcqY3OceGVAlXgOWnmAgfowgTxI4H8tfjRSzy8wNIfh8oG04ZyfGeL1ab3+KLR0mZijz3F3LpZlHBOOT4yWTSG+ty7S1vT8qTyuzPbm/tWRLN8CZ3oOAb8FZPLOmLnVB+AlG9XXNJbhCS3HyxU744lNwb/44Yn6ysPompewQs8wAxOd9mb/uRFcvmYWVkSoNyLfPF1+YXia13wHC07ccA75idX22Jg2ratkav8CYX2KKXeeP9xI4W5TmcI4ilr9vba3JIaZQtXyeTqDrgqyB82Vq+sYOR7yvlceATO9bmV4odcv4yZQN4P0Iqvx2Ppdguxm+Ca1DYa7Cw0SvFeIY2oQGDqaYrMCGowUos/hZnSnnPfs1X01Vix3WHyaDxZoJn7JhlIxXDKiiPVZA3npkvghXYsDBuWrbTIzQmvFxN+HDKhB2gyc0LmAkPPmlU9fu4FEZ8ndYI8vgU/v61YSMQY9fki/EgFCsO9djaokD1PIOX4lPFeIXiehNbwIyvic2goTm8rdAe2y6xoMaD+Xm+eEAot5xm7GLXC9iXYpy/f6W3vDU9mMp2tLzD9rYZFqwcj+XPy+Cat7TL3jYMkE1YPN+4HtGyHSVwggQgECR3DYnc5e2Q8sTWMxZ7+ys4Ubw/M/++jMTrgloYLKBrr4jpf4ByJj02Mdad2IW/tXVNzNHe/tcBtMKXY2nBOpYZ2i5o1N6GvQyx8fap+Cs+XYQGlKW0Er1/oIyAFBIj4QopCSf2PXABy7RVXiB2CSit2OVmebhZHtu6J0MavthBMfap8iGkuMnNtNIeH4j1tByaoIc1RQ9rit3QJHxQdXmm7aJhAG0Xd52AXqQgVaJjQLr+hiUaY79hqz23tyBd7jxWMCctWKcY8+WL4L06/iMfHy0Ai0HX5VzvRX8DNQ7JY5mJ/mLbsASl9Yr9ntYMjP2OOC7hi30C3gR5noMq5PRyy4mUz50kxttI8sSZdNHfVFPa2tiEYPdg6A/UGNBgYjfll2jljmJSUJuiL367zTf9dofsRG+X5Y1NhG6ztQvc7+22xBDgqrOPbqPj5Ph0X6xHBMuDzs4be/E5Yoj22R96LS/aH9kqPpekn9Fi7GVf6Uf2RzptnT6756Py9o9JBwbOYJPK4i190f6DDZD6vI7rDhD/8FtiXtNJcWJnxXFnxdhnYuuHYOadcpYYGwcKLoVW9XMyNt8BZTiSISZ3yHbKZiH1cFIejlU2WIwDbBO7yKqE2HEDeBXRRlw/+pgCsfWs1Qt5xM7Y7/k1Tv5pfyy2/w2jWsWYReyy0qgzIdprkJ9Ndojx24BYA8nOtNFpw1YbXgETxDLEXohu9saOdH+X5OPraLYlNlKunufU1C8lKjpm77TFHsgvhiziNOjuF7d1LEzGHO1/u6tU7PhjfhGAyqAvk8nuq+sKVf2XxwvBLchXeZPltugYLzojrkqjP/KBD9h0HHsksnDmhbKVl34VfQlqs8c77qi39ZMeEXuT8g65n8OHqoaGgZWeAx0ImJly+3E0NwW8tC8Wsc3ryNwvxmY5sDdzqsaNfrAI7BFNp0R2iliU4aK+KH50RxMwtdZT0NvcCr7oKIwQEpu/gULsDy1BX6Iq5StINTELkQtOZ2WSS+d3mM6SJPqi49QdLYJeQClAuO50L6zs/gKQpZBh4imo9r66WHz+A11J8efYFR+W80lFjdJXlL19IWE8qgz8XONz1gJJ+qZzOh1vbAe6mCKsTlGMF4hxtw0tu0Qs3W5vs1sEMj/FSthzBfGd3vhSm3f6Uoc8AseiMFIdLra+YPPGltpIndSR8W85jFhiO31q+96utu+E17Jd175f85UeUdv3EZC17C+kgV/JN/Dtq1fPUzv/N9AsYy9CDlgS37iT3thub+dZKMhOsXV/j8+yHwuVh9odSLzhWeVO0Mb8jpu+sKGF2nCI894xqBYwxqLy2JXe2M22+R2Zh7yxOQ6xdbtNLA3ml9jb+0PW3UOg7pTRWJFrgUw8nU2rrcAL7Sd+p83bemeeEL0YnaoNVdSOyUK13QFheeyL7sG++HVjsYW7DuMgBsYjovLfY6i3dPc1Mnoyk3aUxcfoyIis3fpKz/jii/Nh2LcM1OntmAsOVBE7FYhbaRGfO03VNUMc84Z8EQx7tkOP9vnqi7wdmS9AXa4eAH1QTEncRXzR7Fch+d1i68HTYsfNp8XObqvHtVVMbpP7Q65i6ycW+RK7wyPYHeWOMnuuFf7mOco2ZZI2d8oavn5+x9oXiuZ1BLcX+cbtgP4BmHcC83577tyd9twF+4E+BrQA9DF7rl1s7XKDat3obaO7xNKXYeRKOtWT4rgXwHzATD4FF/wCLVMGGlaWCHqeCu7VIl+OTlbOEeNF3ljxy2Kyk7jLvqjWk5nhad4O38t5qj+OO8TYQkWMV0I9LTwGIdLgwyrzxFiu2NrphHhOX2lP9G3s5mPHfPHifHmsmBTzomCj232xXd74dfl0DPKLI3TM9fgRtMR3yazBhSNm+4MurJhNBx765RCX1Bxz7fW4/gadTRzGSXX4SflfGKOeFEuV6FyxdJ+9nYyoSv9ub3+IVM6gVWLsJe9Ximh5GY26U5khdp68TLS8IDa80O/ln0xPxLGdadITS/dE50MS0WkQfSqL3pEZVieRnT2X4USyYSvGF8d1Yk/UeXaGePdBAlheg7rvruhNz1f6UrTcm+zsvvYbp7ddTHb5Sr+yP4DrP93OLaglpfhoMrm5coFbwJFul/IjILv/QfSzBW+FKPmHsefO+us0J1SZG+prQ1FttUAGhDvA+tbdXiLIWffPmtV9KbaOqYQ7AziLNrNZW3KnffMxmpZyFKupS9l4BH3ox/JYb9KX70AnSitycNm6tfk2IZqlbD6MzfYTZcchOqFZpgRhLgMN4u4Xce57Y9lNZcvLbi6Tlm/jewp72xqQyaS3SNRatP2TvS3YB/cNadxSH9zz0rgX9cF9fRq3pw/uojTukj64r0jjHt8H97A07lF9cPeHa2VsJgxDyfuzVk5xCmX3zZ6Yl/gedKRcb/yb41xvPAYqMfH4cQ1DxWccg4AM132mYVjFM3zQDQy1Wob8LziGzcgwRFuGih6O4WfIcF2PhmEpz7AWGWZrGQad5BhuRIaTX2sYqo9xDNciQ8UxauJnRqEzpaMMMvVNjLIShM6DoaMZAR1NHvRU6jxqb4LOo3YlqMmLyqUwRU7sILMCTGCfRZckmeZ1YQ3CUASmcvhLPxxp+0VaDUf7qOFqkgfMDLdgJSuXdJOeHWckONwlM1UYGMWbFeg3hoodfyGwUkSKTInNx2Gk9TwuAyvPKb2wiKsmyiWHNDOgeiLyNnQm7ZtxwhSn+bj2JvZmqGLXqgpQFy/sbQsRIjPRuda0ia297VCGXuQXMsxFfhquKYVQ1ETRKXQ64PloxkSfNGNaLG0uY7P1uYSt5rksx9+pacDglNFkJWjPte8TtdavuFQg60k3k4HIMp108owLnnP0ZrZBoSbWjJm1rs3PE+RbcJSZB72qLSrRn3HhW8uvAPOLQz7K2YN0eYEMsVYSyWq+Tck2f0Ile+wgNzpDeRw44M4H+aBSt0VHsNY2cN3tpJu5gUWTDqrdTNYwjAe9kDKC1AxUP7FV5HoHuBOv2bCFgDHz144qf8VrK2zMYgiMo9onAE7x/Bh5TmVgfNXIUmnfgdfePctWTwwYbkKGuWepd/nFcMyoS3l8OGdV9oceQcNXVfJfIFNiXYa2REeVoZ+QpUR72ymY9eBcx97+Gf7SzXfahqY1ok/7MO+3rb2tF2aYvMPQr7mRJQxNxTdqKn6uWcVPMar47QdoDf7sY27BktwAMuJ+/ABOoDPzqxfCBAo8Ey70bSae7gwx0PHgUqMTUZBniP3AeKfjL5n4O/7HzJ0QtL5mURYBa/dY6iP6Ex9xVCk8QF0diRY7AoMyJX6A9g2biOf4S/6TmM2cgxoHuPJj9K87sD7aR1uoCpEPJoqJ6b3uJ+uuCTD6iqmlGnzfBDYYiz1ACofqxmwcK6pJEoJF+PYasZ9olmawE4d+IMsxlGXAQSoz1q6y72M6YPsSQvefLMRNnxVUN/2FYOCm/yHoLexpwdzCNgi96vHGsrFET6pdUtcctjI4x9jC7G15ab3gkT7yekcwdtbL/kknk0UfQdP680ljG5v8T2qRA4HJ3XYYZ7efKEcwJgyqW2DYa2/bhAuJMPQFzTxtJVOP/G+tuv74Ea2IBz6kDaKFNIg5Jt3PvR+R0f3o8Rr7Khj/f2hfGR+Z2NdT/+Ts646PNKsphR+StVOYEMBEv5ysp3hSi6RbcH6vTP8nuzdDVgfLSUcwyBcrSt2CAtAGUdjai4ct+CpebHPEQ+5HmyIecjeZIOo85HNp9vuQuU1138Ha8h0CHe4d+oDrGe76kDllXDKgWf7utIFT/i+rPsu7+3DKQZNKf3g/NeOGD6g3XA/ecHMRfD0vlLsFNJ6HiHrZimpvH7RnP+3Fm/+XevGeD2jT2fk+td1m2ovflF//v5ThD1iGEsuwXs0Q73jgsAEyHJUaof94P+V2MW5yn5PdwSPjqKLecVTRtzmO2v8+HUcVKc/uoyM3mHSLmE0JyfF6+lOXo1eT4xVmOebS4c41+43dWS3Lu0S5dh/9ZVOE/Wxo5DqcGGLiBq95nxpZJsRKfATTpjrt+ojmfratHzr1L8XYdfll6+6wCfa2dzKxxd3h2LynApcmnsMVe6WHSN+TtLdNy9LcPRy9T72hM9z0FlOnSO5C2jyuZHf/uvXeu7sEvK+trmne5e3I7Cden4Rhz2Z8QLLM7vuKLO7GHTgydCin3gPu9q32tnsETd6/ek+dxPyVLJMW4Hpdhwzjt45H8xWYJCgL96XfeRRj+0h54jCOPKIkUcngya4mS+75abO49lfYOOPZvaBIsp5Ly1aivAWJQ6naS8kILDPfFy8iU7R6BRL8M8nKXrGvtaVHaBmI9SG/T/wKTvJsYofvsuT9I22cNG/vVW9KsVXf8fbNu8h6GmSPd+WPoUT298gTAZpbU97YofLYUS6p+/fqFLO5kt6KRcX0YDIl7xkqhiwHxW9Q8JZ+eUeT4p2+VIna8ZZ813tE2Ee3dVvJXU45jyhsCLtbuB2mS/i8wrt0eakf6WPli9v2lsfOdE9IW+/TdLrAEp2Jvq8KYrftxdujNnvbbrw18D6939KTelCjnhjNsTJ7ZzZ0mplgvHEadN+gaXN1fJsjbDToXqxhqzZjqyiLZ3eIybJYDgj90BhyP+MotjB8yk15GQqaGJTULEhMZ3dBCMNvkGGcluF/znAM9yHDf5KbuaCMu1/EZsgtrcHIlCwx7BTUJYYdgtESw4y0XuliXa/ECZUQyF3UHd13wJfaAXbf2kt8oHyf1d+NpP6ii/VVZW/7PG0495LFPMc/WEiOqfRz32USx/PQzTcQN++/gH6FryO9wyaKnfgO7Sn67WE5ddE1XGh/L0LmdHHl+Xdo++jKUKcjzkx1OtL0Lh37EOTPuKKCD7Ip096htVeQSecUeRAqn7+jmVNctIc8KFDenrS338imZcgHfi+xGp8bIhlcn5b5fVlq5p+9QzMnyF7M/BJS3j008/VZNPN1ECpRbeaP/aM387ksc+TDzP3pwxGiLOseugTy7m5c5EufuRGmff+gw9o/IdMMYOrGKk2soFULQ9ibnHQIixqDIWzA2TuEJRDeVM/sHcI2Z+rXc/47bTj3A8HUprqjNNeDo2muqCrI9ejo3lwJBLmiutRc92TpBs53aYzsu2a5zTVSycu76cAZxVIHztVoEN/fQ+uvBYnZoLju7xjFv5/FxwKq8V/COnWx+PuRyPwHNeWRLMz/B+3XTyPNTMsb64cJ4U86H9M+NGUwH/tdmrLb+1B2RDUjlhH+PM+MXknzFL/sw1N0WIxNVHqbTJN6LtPYmGXUhdnYv+RS3nvLpLZbd3O1vfRtzTSp31vnnCYN3W04TSrBG7MwTZprNk0SY7Pw5q29rZZMZhdA7/A9MpfVPsLWdn1a53BRH53DWcglcbdJLbyzi9RCeKSmzd0+8gLb3L9SC0t3mbSZM29xbWbnLk0t3P3mOWvhwbf+xVoYZFFrwWoxqIUDae3tz+btLfGEwLyqOlmd8QY3WX3zTeyeIc8D+IAkyXMv/tLn+VRanuv6aONNRur+5A10Nklly05Ue8ZWnKiuq3QL3dcYcT/HuB+m3NppLfquTW8ady7rWMRlEDFhP0Wety1bWiW2Hsrzxs564zc7cZwwnowTxqY9GfAUezp1+E6cTs+hz3DEb87rK87jLM7B10mcPBbH0VecNhbn9zQOHXTHR2GUy0mUkamZ6tE3qLP+weupB4bE1hfzbiy7WXO/VF7SWxu+/Mw4/HVrZ40LeYZBwDCo26NhqOAZhgLD0O6Z3HDzY1yw7ijOVy5D1e4+qxmLniIXZZhQJqGciUPaq7lJetWhfIhXrUkyhTSYP1ZCHZXHv0NMkqwOJhfk2dt/TrQz2hsP2cTSbnlV2V9Qkd0lmtJflC4/1+yvIiX3Q+7dI9f74uPxsZ/LyWM/I9XHfnyln0SfxmX1y14jNkc1vQ2y3Bd9FbLHyrFhTZx5lZrYl6/yNWLjRttp8+OlODNeRwY4Z8mULg8NFt9AST0QfQmUTSz9KQHlQTCCR3ao5eXbxI6b8m1kOId8o0H7mx/Gkdw4hhx+jS4vkSEwWg5ZnML17rWZtricWYAr3fUoeh55Hvg1eoMEZHkfF7d/C/SOtvzVkN1VFIeiIfU8eajgodfUQe7br5EVbjYhvi5fmf06XSAG1eIwoh304Tq8Gd/GfB63vEAs93U6No1n/WCYU10DH/zDYaqf92XacPnFQT387Pxl5+ve11qIv8Egzb234Crj6lfpyo6D+na8HZf/OpW8Wjn5Km1UVlq87uWkjOe/dHvO3L9+hawY29usSTrG2gQ5Jr48S/xRlRg7lRqt325TTpNn/j+4MdH6quH19+h1pfZVxnf737EBpexLz///GH+xyj+/b/61jD9T5R+B/Cn29ZXK/XBFCbyCpZstCNBcY8mypd7YibIl3tjbZYt9HWMFh1NYInZMsEFY5Rt3AOb0nWcy8I0txfMyXREZlXr+JfapL3ZiNqSRHPoeNDELtOrop6QNLVcb0TauvMe3sXe/2Kte+J7zxNrAqokRubahSXAOEPiNBa69NhJdAT91IL78H2oCKuqXnU3RYNDZFJKdq2qCDbVCQxMJncEGORCuCTrrQmFnMNS0smCcc3WDXO/Ed+adrqJrrxK8Exc4Q83AhC/LO+E/eUe91lnXEAwI4fHCHAidY5CliaSCm5dA9sKsUDRY23SVzK4gV+/7ahWuSdJc34KZZT5JqpBcJc1r5PpQU4Pf5ZKkFdGGoNzQJEnT6qJNfjkUdhUtrQlGAx7cKoK91PwMe1/ascDdZ3pTcDeBSHoC5+CfXCXXNNXihg8sSt/8pR51MwHPOeRT058J6uUjNbP3rY8xedT3tVPvTzJ6K7vurHQbXl/PrrtNrlez69W6632Xd5p3Aa/8c8s31dO0qiEcamoMNMm6mNry7Kw0Lo96fSPDHQvdhvvHpfRQzvTCQv2+RKn3aBdq+SvPwb9Ol/46Hb9lRMb0tezd7ft2JJMv4Tu/0PhbYJZQCiHe9ysA14LvlPTgLXkIN5wAHMKSnmQSX5jI+xqcLIQFMHTDdz5ECHERugVf/oHwSQircVEawvX4ZD34rj3spfmh6n6Nty0SLC0Oy4hB/WzrLf0cQ9n7zz/+WzLJv7drzE/fNUb+TdshDxwH5Djm5OTNsw9cbVsnzBg+/erJ+Zfz+0Rm3FbpIyn0y8CtkjLUdIrZe8sOkL1zlCBkvrLYLZTlOGbm5M3Mcc7MKZiZU1SWUzI351hma78HsjuyHsx8KONeK4l3E75/qySTPxsE8e5bahxva44m3tBUebTyjGRl7fkimXwUO/WZOY6ynLzZOUWtGQ9aaTlxv4MWqIs3MIH0vMpy3JqsyAdly4T0nF8lk4Nxp4jqG9RyluU45+ZszGjNfBC4sVw/xffFoW4vY+m3Wqn+/4j6AXysDsdXYgoM8I+xPRvgp/H95q5kcgzD1X0uP4byVQJ/QKByP2T15OQ9mOHJcXZkenIKHsgSc4ruzRZzSlr7lee4gygpyFtAZAcNgCw2kv41aIOQjlXXJpIZz7auEzKezhjPNgOI4tctjHgAv46w1/i/j3Xgt9A9Bp7EK7idBr6le3wI230QX+k9g8R2dmUl8h6x0tRewa+iDEoo+LU6g8bpPwys+Am2XVcuEp8ztmvxrdx+mYLwsLrjxIYs2kL/KxfYnmPEH/Bl4L9m030jsjGVqf1paqfxSnl/mo+E7yw7YMj6CJYRr/wSiJWqMvoPpBtJDMNXl3Pha766bcVNkImsyrMTiG3qlR8OoS+Fr8Iryy+iJSBsK+DrqMq28BK21xmuX8YuoRtrfInEy/BVo7KNH0G3pujEl4elkSzOKKb9SqtmZ9dkxq67hYydhHhXleFdVnUhfB4bnwlBgX6F6cuMOIPEbyx0zwYrsh230Dh2JPAtSptaHgfbGs6N04TLs+g+APOQqMjiNiPoYGwz8covGNvWbLa33P+oqd3Tn0o3HL9sAymxEZU9BL7ilpRN7hQyKojW1AzwB96CTSLRye9/sYtt8vFzjP0B28nhVxbGm2MR/v359+ffn39//v3596fvz062f/sxtl/oMyO18wiLSXg6S0tnZ2vpKxit7iFVkkfTVfeOKq6g9KXqPklsH3F1LyR1byh1LyWFXVfH7+reV1+eTYbICMnqTu3fReaZ/d2pfc3oAJvS6h5Yn7AL6t5X6l5OF+v0k9G7YRbbUY7tT5SlnY+oe3Spe0X1DHFr8D25bk25nUxR/XX5n01SeUoYf5LRajmOMfpJh/v/1E5S+9jrPqtYvd7LwsdY+AQLn2XhDhbuZuFBFp5gYTabjw5j4ZUsnMrCOSxcysI6Fq5i4b0sfIyFT7DwWRbuYOFuFh5k4QkWZrP9foex8EoWTmXhHBYuZWEdC1ex8F4WPsbCJ1j4LAt3sHA3Cw+y8AQLs1n7G8bCK1k4lYVzWLiUhXUsXMXCe1n4GAufYOGzLNzBwt0sPDjC2H7mzpp1rbNgyYpokxx1FheWFBZPmBQllOtOV3FhUXFh8TiKC4zJH6xpWulcFQhHcHltcuGUwqIJxTTKpDvlcDQir5nkLJBrVkYmLvL4PGVVHmnylKKJdbgR5jhnAa7T1eKqnM+3tJxGHycIhZE1jXLNCgjlMA3r1V8NTXIg3CwUNoXkQGHZTO8ESJpRK5uihbj4VjuhoVYgVH1NpF4orF3TBOnRUA7TK6zAGkKCa+FAsAYZ2a/moIxZNsC3HGiBbyh3A1wL1dbINUJhoF6qC9c0BqT62nAvBYn6/WwTUkkm2yKTNKSacLhmDU1D/X2LP0wKVtPY4Id4IZl80XxpHisiEaHQH2rEtah/uR2PYD5a9WO952kIGv+q9//q5wpBu+dh73kVzK/p+DN1tEsXX2bxZW59oq/4uD5wAnygGl/1+xsYUM/wLF0/kVr3Yz7fqusXVAe7lfUL2Ux2m84/L2WsVl0/s7W/tl8x09/NzKer8VU//iTr8Nbryq87NkS4lfURqfpj/UQJ2zRxo9Bb/gwD+W9jOrXq+qU9udp+Sa8/Vf42XXy1n+sZou0Xs1jfr4//oNB7xgo/LijJ0/b3ZvUf08WvZvGrWfz1GVp+hy58VBdfHfccYwOPmZOM46ufn+jiq+OY4gptf25W/o269udm8d0s/oaMvvN/Uhe/99wXSq89R/7P6uIvW+RmoaBph4JJ+9mqi4/LozRk4zRr3/m/ydaaM3TjPvVcGb28+vzxYVA7F18dFyrLjfn19Kes/KnxFIt/7DzjH+XaFj8uUs/9URWTrYuvytWjy1/df7dH6jt/NTyji6+OSwUW7LH0HT/boo2/h+3buKfm/PQ/iC2opfJn97EUFr9eZ7/6/iCX5V+kw9X495r0P2qYK2j31VU/TSuY/7D07X952+U/4q0sZJvV4vJjuYH/6m+S//rbaPjz3L7z7+uTAdxqf6zFral+VotnpPpPLZ6Z6he1eFZvf6fBs1P9mBbvZzjPyACtqP2OFu+f6k+0+IBUP6HFB6b8vxYflPLrWnxwyl9r8ZyUH9bi9pR/1eKOlN/U4rkpf6jFh6T8nBa/KOW/tPjQlF/S4hen/I0WH2Y4v8qA2aTqH7R4Xm+71+CXptqzFu89/0SLj0jDLMRnf5bU43Qv2XQ9eBiOt7v4zw0Mx9tL/KeBtL/eelT3Gr6b5D1cCOjOUXmG8av3LdW9gz9kuFOHX2yhuHq/U90r2cvwZpHij7IMIgyv1KWzkeGOeRR/g+FfMHzndIr/jC1w/NjK5GL8g5mTedFK5arVybWL4Hahkt3PVv0unoeDuHrfVvU7Mxnu1OFRhlfr8CcZrt53VvH3GV6kw/EcM8TdunRKGK4+p6Duvb6a4er9eHWv5F8zXH0OQN37+F2Gr9fhg7Mort5HV4dfsxiu3j9X93oOMVx9jkC9N/wzhj+zUMv/KsMrdTh20ETPOvyabGP7n0b409vv7Gxa727dutl3Gd6sw4MM16+z3ZNN7aRGZycPEzzdn2xi6ezUpfMi4U/3S2Zy/ZPw5wov6dr1ZybyCib+4QzhT/dLF5EFsIvSyp/PcH05p/XDdNL9obsfjiXS/dv8fsbnSt1igj9G8MFCEesX1LHAEwzP1enz6X7G50cdMkk/12aMl9qMzyUTTfCbTNJpNsE7TPDNBE/vH1804U+Y4GdMcEd/k3MOTfAbTfC1JvhjJvgWE/xTwC+3Qvti/lxd37UMMD6Pa/YA43RuGGB8TtfaAcb1tWEAjk17xxvqvOfXJunvMMH3mOBZA43xSwcal2fyQOxT0tuL2ySd4EDj89AeNuF/fqDxuW2HBhqfYzZkkPF5blMAz7VeKii6cpYNMs63ZpDxeWgtJvw/Yunv16X/SxP+ZwdRP7CV2U9ArS8T/isGm5xLOdj4nLqlJvwtg5FneJoe2kz4fzHY+Ly7t0z4vzDBL80xOf/QBL8xx9jemnOMz817zCSdp0zw4yZ4lt0Yv8xO9VYf0OrtchP+lSb47Xbj8/T+ZMK/1258HuAAhzF/gYO2R339TnQYn9dXaZLOEyb4cyb42yb4YRN8YK7xeYZjc435v2OC15jgsgn+w1za7nDbePx0ssNMNhDcYJ44MRwKyROb19TI/lBtIDyxORxaEQw0RiZGoo0N5LbDpCJX6UTPRDxvqtDf3EyOm+LX5IvSEFcaMkVIPSUaia6QvFIqNel75/UIsK+4ItRED3s77yd8ZxfR07wu5BHcbxRn0nnEKcYHn8+LU33I9lxFicoNQZA3Ul8TDtRK4UCdt0qeuiqAD0p7K6qKJJoaOeyuqsZbNUXyeDxqAeafj85JkdVnr0vwce5gQ1PAH/TOW9SbPmHyYNKL/cFIuI+UPKkkIs3ICiWr9UyrC4VX14RrvYslT10zKWLzgqpSqa9C9grmXxVkZ0b6SiSpIURuMOHJgv/CY+V9RTd6ivw8+PVPeZ9PFN2D5+cRxeBZ63PH6n2i+9y8pVoRqv41JVddoJKrLlzJVReu5KpvpOSqC1By1QUpeekFamnphWtp6fkW3h+WI3K0rq7QL0jSvFmLJJ+3arEkCb1n20pyo+THM2wjggEkSbUhaWUwtKImKNWCSUSkmmiL4A81NgcDcqC2cGppySRjJqn3Tq8Eig+vEejd4tpoY+MaiMJRUu8NYsYqSXMWlZV7JE/FbDyhl5Sc/WZSL5gzp8qzWFpcNtPnQQ5NErVagBy+KEizv1tRVu6dJeCtZRXTHwjqdvNHKvZ9zKqOlx706I9EieRCKocLPEtUXwLDw3jTiml4XLCGq7D0vA4+JsdmpifPHc5poKI+TiTWlsHlEph2jA/41KZNj9JkGDsZk5zPqYXSjtjUXe7zRFW9NGlnk+pruff8z/RsTE4LTq9S05N903LDJ0ygzoNBKXUO8jc791ibMjnU1ECA9HORdSXq82DsBRJ5xU2KRgK16ech60oQDgTSCtDXqcXa6PQ8Vl0CfZzMrW/0podvG5l32oGzhm7C6GxtPeN5nLvsdnOnv5qdopuWbvrBzHpTAoWoPjTt8Op0CyWnGafD3Gnc+vRrIyGpHvpmUDc9PtewlaJ/ZEO+b/HUcL2nY6fv6u1Le561Xrr0k6D1Iq6Aiuq1odSR6eeoZJMTktPqWXuus6HfSTvkOT0R7UHYRqloz6LXpmB4gr3Jwe86Z00OQzZwKd/sAHSdswiE6vTmlDomXisB6f2/2fHiujzJu7JpJnTep3sbdOTT+I6cVKZRV9vXyelG9ckdva5TBXmIzujM9HSz+RbOBjfoSg2kY31immvUHMgN19gB2aRwU9HsYSqe3h1xR6cbjIno4ecGhdCfDJ9uys1remveVZx+wLh+pNLQJFC/9v8B5SQ6Si6MAAA='
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:
            raise ValueError
    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 ** 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] * 1000005
    check = [0] * 1000005
    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 == 3:
        ans *= 6
    else:
        ans *= 3
    if sum(cnt) == zero:
        print(ans % md)
    else:
        print(0)

main()

Submission status: Wrong Answer

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:
  mul = 6
  
elif num_zero == 0:
  mul = 0

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

Submission status: Wrong Answer

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

num_list = [0] * n
pattern = 1
waru = 1000000007

for i in x:
    if i == 0:
        if num_list[i] == 0:
            pattern *= 3
            num_list[i] = 1
            pattern %= waru
        elif num_list[i] == 1:
            pattern *= 2
            num_list[i] = 2
            pattern %= waru
        elif num_list[i] == 2:
            num_list[i] = 3
        else:
            print(0)
            exit()
    else:
        if num_list[i] == 0:
            pattern *= num_list[i-1]
            num_list[i] = 1
            pattern %= waru
        elif num_list[i] == 1:
            pattern *= (num_list[i-1]-1)
            num_list[i] = 2
            pattern %= waru
        elif num_list[i] == 2:
            num_list[i] = 3
        else:
            print(0)
            exit()

print(pattern)

Submission status: Wrong Answer

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:
  mul = 6
  
else:
  mul = 3
  
print((ans*mul)%mod)

Submission status: Wrong Answer

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:
  mul = 6
  
else:
  mul = 3
  
print((ans*mul)%mod)

Submission status: Wrong Answer

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

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

sum = 1
tmp = 0
for i in range(N):
    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
    sum = sum * tmp % 1000000007
print(sum)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 1
x = -1
y = -1
z = -1
for i in range(n):
    pos = a[i]
    if pos == 0:
        if x == -1:
            num = 3
            x = 1
        elif y == -1:
            num = 2
            y = 1
        else:
            num = 1
            z = 1
        ans *= num
    else:
        num = 0
        if x == pos:
            num += 1
            x += 1
        elif y == pos:
            num += 1
            y += 1
        elif z == pos:
            num += 1
            z += 1
        ans *= num
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 1
x = -1
y = -1
z = -1
for i in range(n):
    pos = a[i]
    if pos == 0:
        if x == -1:
            num = 3
            x = 0
        elif y == -1:
            num = 2
            y = 0
        else:
            num = 1
            z = 0
        ans *= num
    else:
        num = 0
        if x == pos-1:
            num += 1
            x += 1
        elif y == pos-1:
            num += 1
            y += 1
        elif z == pos-1:
            num += 1
            z += 1
        ans *= num
print(ans%1000000007)

Submission status: Wrong Answer

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:
    x = lis[i-1]
    ans=(x*(ans%mod))%mod
    lis[i-1]-=1
    if lis[i-1]<0:
      ans=0
      break
    
  else:
    num_zero+=1

if num_zero>=2:
  mul = 6
  
else:
  mul = 3
  
print((ans*mul)%mod)

Submission status: Wrong Answer

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)

res = 1
for i in range(amax):
	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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
L = [0, 0, 0]
QN = 1000000007

count = 1
for i in range(N):
  if(L.count(A[i]) == 2):
    count *= 2
    if(L[0] == A[i]):
      L[0] += 1
    else:
      L[1] += 1
  elif(L.count(A[i]) == 3):
    count *= 3
    L[0] += 1
  else:
    if(L[0] == A[i]):
      L[0] += 1
    elif(L[1] == A[i]):
      L[1] += 1
    else:
      L[2] += 1

print(count % QN)

Submission status: Wrong Answer

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

c = [0, 0, 0]

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

Submission status: Wrong Answer

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

if num_zero>=2:
  mul = 6
  
else:
  mul = 3
  
print((ans*mul)%mod)

Submission status: Wrong Answer

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:
    print((ans * 3)%mod)
elif cnt ==2:
    print((ans * 6)%mod)
else:
    print((ans * 6)%mod)

Submission status: Wrong Answer

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

if num_zero>=2:
  mul = 6
  
else:
  mul = 3
  
print((ans*mul)%mod)

Submission status: Wrong Answer

Solution code:
import sys
import math
from itertools import permutations
from itertools import combinations

#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))
div = 1000000007

r, b, g = 0, 0, 0

pat = 1

for i, a in enumerate(A):
    if i==0:
        pat = (pat*3)%div
        r += 1

    elif r==b and b==g:
        pat = (pat*3)%div
        r += 1

    elif r>b and b==g:
        if a==r:
            r += 1
        else:
            pat = (pat*2)%div
            b += 1

    elif r==b and b>g:
        if a==r:
            pat = (pat*2)%div
            r += 1
        else:
            g += 1

    elif r>b and b>g:
        if a==r:
            r += 1
        elif a==b:
            b += 1
        else:
            g += 1
    else:
        print(0)
        exit()

print(pat)

Submission status: Wrong Answer

Solution code:
import sys
import math
from itertools import permutations
from itertools import combinations

#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))
div = 1000000007

r, b, g = 0, 0, 0

pat = 1

for i, a in enumerate(A):
    if i==0:
        pat *= 3
        r += 1

    elif r==b and b==g:
        pat *= 3
        r += 1

    elif r>b and b==g:
        if a==r:
            r += 1
        else:
            pat *= 2
            b += 1

    elif r==b and b>g:
        if a==r:
            pat *= 2
            r += 1
        else:
            g += 1

    elif r>b and b==g:
        if a==r:
            r += 1
        else:
            pat *= 2
            g += 1

    elif r>b and b>g:
        if a==r:
            r += 1
        elif a==b:
            b += 1
        else:
            g += 1
    else:
        print(0)
        exit()

    pat = (pat%div)
    
print(pat)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
L = [1, 0, 0]
QN = 1000000007

count = 1
for i in range(1, N):
  if(L.count(A[i]) == 2):
    count *= 2
    if(L[0] == A[i]):
      L[0] += 1
    else:
      L[1] += 1
  elif(L.count(A[i]) == 3):
    count *= 3
    L[0] += 1
  elif(L.count(A[i]) == 1):
    if(L[0] == A[i]):
      L[0] += 1
    elif(L[1] == A[i]):
      L[1] += 1
    else:
      L[2] += 1

print(count*3 % QN)

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
N = int(input())
A = [int(i) for i in input().split()]
count = [0]*N
dp = [0]*N
dp[0] = 3
count[0] += 1
for i, a in enumerate(A[1:]):
    if a == 0:
        dp[i+1] = dp[i]*(3-count[a])
    else:
        dp[i+1] = dp[i]*(count[a-1]-count[a])
        if dp[i+1] < 1:
            print(0)
            exit()
    count[a] += 1
    dp[i+1] %= MOD
print(dp[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
    
    
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = max(a)
mod = 1000000007
memo = [[] for i in range(m+1)]
a.reverse()
d = {}
for ai in a:
    if ai in d:
        d[ai] += 1
    else:
        d[ai] = 1
    if ai + 1 in d:
        memo[ai].append(d[ai+1])
    else:
        memo[ai].append(3)
ans = 1
for l in memo:
    i = 0
    for li in l:
        ans = ans * (li - i) %  mod
        i += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
mod=1000000007

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

ans=1
c1=c2=c3=0
for Ai in A:
    if c1==c2==c3==Ai:
        c1+=1
        ans=ans*3%mod
    elif c1==c2==Ai:
        c1+=1
        ans=ans*2%mod
    elif c1==c3==Ai:
        c1+=1
        ans=ans*2%mod
    elif c2==c3==Ai:
        c2+=1
        ans=ans*2%mod
    elif c1==Ai:
        c1+=1
    elif c2==Ai:
        c2+=1
    elif c3==Ai:
        c3+=1

print(ans)