Problem:


Score : 400 points

Problem Statement

There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.

When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).

In how many ways can the knight reach the square (X, Y)?

Find the number of ways modulo 10^9 + 7.

Constraints

1 \leq X \leq 10^6

1 \leq Y \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

Sample Input 1

3 3

Sample Output 1

2

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).

Sample Input 2

2 2

Sample Output 2

0

The knight cannot reach (2,2).

Sample Input 3

999999 999999

Sample Output 3

151840682

Print the number of ways modulo 10^9 + 7.



Sample input:
3 3


Sample output:
2

Submission status: Accepted

Solution code:
# compiled by pythran
"""
#pythran export main2()
import numpy as np
i8 = np.int64
MOD = 1000000007


def mod_inv(mod, a):
    old_s, s = 1, 0
    old_t, t = 0, 1
    old_r, r = mod, a

    while r != 0:
        quotient = old_r // r

        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_t % mod


def get_fac(fac):
    fac[0] = 1
    for i in range(1, fac.shape[0]):
        fac[i] = fac[i - 1] * i % MOD


def combine(m, n, fac):
    return fac[m] * mod_inv(MOD, (fac[m - n] * fac[n]) % MOD) % MOD


def main(in_file):
    stdin = open(in_file)
    X, Y = [int(x) for x in stdin.readline().split()]
    m1 = X + Y
    if m1 % 3 == 0:
        m = m1 // 3
        if X < m or Y < m:
            print(0)
        else:
            fac = np.empty(670000, i8)
            get_fac(fac)
            print(combine(m, X - m, fac))
    else:
        print(0)


def main2():
    main('/dev/stdin')
"""
import os, sys
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
if len(sys.argv) == 1:
    import subprocess
    if p == "":
        pymain = "./" + pymain
    subprocess.call(pymain)
else:
    import gzip, base64, stat
    gz = b'H4sIALv6UF8C/+19C3hTVbbwSV+EV1MQsCCDQQu2AqVpC7SVR0obOIEUOrQgI+IhpCnNmCY1DyheRLStQwxFnOs4jr93hjtznWEeV/nvOA6iA608itwZBVREUMAHmFAR8EFBlPxr7b1Pss9pAoXxu/f7v88o3Vnr7L32WmuvtfYzZz9ossxI0mgE+ZMkTBUQyrvJSGAjw1/4aTQL4IqE3vD3ZmGEkAZwCpfPKBgV6QVGWk61LF8yK1eUROGiJKMiHc7yyamGS1MF/mNUpH9fIihSQdBHyyGv2U6KzXYuUaRPMaKb05Tlkli5UD3FhuqXKFIhSVCksnwp7F81w1czueS0nOUr5/Ljp/KErwa/r1lE4TWLjIr0CZbvCVW5H0K5NKHnnwyWzmP1JdLLoWRBkcrtMN7pWDqxcLyzZpzT4fI3jmssmjhuYmGu152bT3jKYHlnzpkfbe8kjudBDIfPGzq3DO/33E2bq96/4dR/P7F2bfbbd2rxWT4r0wv+NadnLOmX0zsJS67pJ2jw2UT4VwL//vD45Fefsf1tV5+HNkh/fq/g7bHnpHveqtrYtLbFNuTen70w7pfDG7YMeqpfWaP53hdzTG9brqQXDVQ2MA5+pRAfH0yJj9+TFB9/WwL6Zk18/JgEeGtafPxfEuB7Jaj3dwnyG1Lj4y8nwN+RgH57Av5zE+TPSpD/jQT6n56Azr4E7bIwQf6lCep9LkG99yRo30sJ9OlOUO/Y5AT2kCD/4AT4zQn4fzYBnwMT4Bcm4Gd6An0OT8DPpwnoj0zEfwK7Opig3soEdJ5OwH8oQTuOSlDvhwna8YYE+EcS1Ls4AZ8Z0R5G+SlPQOcU4EcKg4U9LC7LZVsEig8x/EKGP5JE8UbWT8nxvoHRqWT4TIZfBnoYgPkZHTnOz2H6yRhqVPBzO2uXfcOUeF8qpV/H6K9h+EmMT9GpxN+ZhvUOE9ruY3yyimtYey1R0b+Z4c+q8AL0R15fjW3MGOyDJgqStKze7ZK8PqvHJ0mCdNecKl+Rw+2Vllq99kKzy+ErN5iWA756QZXPMAGwDhvk9tit9Uv9tWYbIA22OqtH8nmsDp/XbDOZkGZjo9Rg93jdLqvT4VspLc8jlN0FDX6fyUaozTHkSZKtsdG61LHckA/fvQ7J5rR6vZJvZYNdcrhq3SYsNLvKN8GGKCBtKJAqpBWOGrsLnjt8hC+gWgxYh8tr9/jMTpNpXpW7mglSTNkFceIyOsHmtFs9JniSL5lBZPjns/rsULbGWYm0q3zImK/O414hOe2uZb46ye7xuD2Vs0EGYN4qWZ1Otw3KSPZGm73B53C7SDHDRElyUy3JnMVjYB7gCiiPLLe5WqrOk0xVE6XK2VUFkpPKMRErcdpZSwBiElGdwWAojpV2uJYxGnGqqrJifWUGFLaACDu3we6qd9fYmY6jFPOjTQwEE5MyFNQ6XDVSrcPj9UnuWhOopL5exVxPSeVD+9ncLsjnt/lM9Taq+UJZ824/1iB5rK5ldqm23gdV3a8y1PJ8aqNmaHO+Ja6Dm0keO7TXcrupPtqSlI2l1hrJZvX6sCLXivp5oLRil5s+88VznDJDlClDgcfv8jnq7dR+mHVGOWXsX1c7TOLaAdjh26K6+vpNRfa9GJOFK+qsvm4G2FM286CNPfYGp9UGmq1HDq+PEPq6tQFst8bEiEBbXK/uJhLdQdBRq474NmlaagTF0SjgXgaEY0EARVA1LvNSYIdZBw13HHsTePYSRFGuFbrVAIY1b/Z16M7EBKv12JUB6zrbwQYm5LOb5tVTVym0gaf+E63q9TqWuUCyqkIavt0Tap1+bx3RJgZklcdBR1ZP+zD4tswGlSBkEKT5rhXYrPPsXn+9HR/aaLZaN5iNUOuzOyGsYnUQlqVaq8MpAHs+t1Ootbtrhdpldp8XMRDw5SDvszc6fEK9vd7WsFKotTndXrtQT0I/Iuvdy+3CUlt9A2TH2lhnWm91QG2gamFmWZlUkJsnzLSYp5ctXAjfC3PzlaDBoACLBfhWOt0sGXILlMUU+eh3KT/XEPuanzuBTrOTYf6YDGlq9Fsy/JcKs/QU8r0X+ZsEqZZgKIR/e5P8iKP/6F8s24dREsjzVEKR/pfCqCdH1x80wltpsfFb5eiVfQUo7+slP08jYyd83oD/LvwcyPYWVvWiOCuBtUKQwYEHc5Jwhvs0g998/t5UXOHYxOD7SP4U4c8M9uX8VItcvhqtL0k4lxYb3z3x+JNpuGLxOsvvH+bojVp7l+UPuek4C9cKxnPDp7McPo9fXWHjtVQ235Y/Iocv4ee9HD6fH39z+AKefn0MX8iP7zn8BA5fx+GLObw8fkT8HRw+s4Hie3FjWjJ+5vBJHD6bwydz+DwOn8Lhizg8vy5l5PD8uozI4Xvx8nJ4LT8f4/C9OfwSDt+H1w+H78vhGzh8Pw7fyOH7c/g1HD6dw6/l8DoOv4HDZ3D4pzj8AA6/kcPz851NHP4Gfn7I4Qdx+C0cfhJvDxx+MG+fHH4Iv17A4W/k8Ic4fCaHP87hh/J2zuGH8f7F4W/i8Bc4/HB+PnNfDP8DDq3l8CP4+SSHv5m3fw7Pzzf1HH4kb/8c/hbe/jn8rbz9c/gs3v45/Cje/jn8aN7+OfxtvP1z+Gze/jn8ZN7+OXwOb/8c/nbe/jn8GN7+OfxY3v45/Dje/jl8Lm//HL6It38Ob+Dtn8NP4fXW9KlWDKZOWagXxJY2X1Jkn9i0U7tDiEyYDqjIqHL4q7vZCN8QrsMi4eMR+IwqQRhDX3gfgfMRxpAXbiPw7QhjqAtvJvAtCGOIC28k8DCEMbSFNxB4IMIY0sJrCNwHYWQ33EDgJIQxhIWXEPjrOwHG0BWuJPDnCGPIChsJfAphDFXhPAJ/iDCGqLCewIcRxtAUziDwAYQxJIUFAu9FGENR+OxlhF9FOIPIT+CtCA8g8hP4vxAeSOQn8B8QvoHIT+BfIzyIyE/gpxEeTOQn8E8RHkLkJ/CjCN9I5CfwwwhnEvkJfD/CQ4n8BPYgPIzIT+AfI3wTkZ/ASxEeTuQn8F0I/4DIT+B5CI8g8hN4FsI3E/m/RXg6wnoiP4FLEB5J5CdwPsK3EPkJfDvCtxL5CXwLwllEfgIPQ3gUkZ/AAxEeTeQncB+EbyPyEzgJ4WwiP4G/XgBwDpGfwJ8jfDuRn8CnEB5D5CfwhwiPJfIT+DDC44j8BD6AcC6Rn8B7ER5P5P+GtD/CeUR+Am9F2EDkJ/B/IZxP5Ae4cvt+zxIh9DaocjuuKW1DcOsW8MLQvwP5hTtqc3U3NxMX1N1cDr562hzYf48Y+FBs+vhsZbW5o01fYRTEjvbNFkw68oaDDw5eX60XviT5v1AQMApbcKAiTsG/vhu2EM8Gd+69HRGR47UbdpBSsTLbSP6HPiNJ++VkMXBWbA9NEzW7xf2XfQOiFHoxCurya6aEQV7Bf+N8MXAitBoUsDv1HcBoFtOc6vyd61X89tr79B2cDKULqirFwEfbClHqwLFQP2hJTPGpGByeJbYc8WWLTWX6iH+kGLxDbC3LEIs7fKkhGygbMy7CtCOF9BWGNgxii0rv2WEO7L5i6VGs9A+40pZAV+h9aCOeYWF+6Z2lC0rnl1ZXiQ99ugXCmDkQEVtXZVVuu2eeUQgtBkMUO8qzSIDcXZ7VIGxHU9mGw9wQ+gfqMlsMtItN7RliQCt2GMlobLcxA8oZ9RhHISU9UWcS8P9ShH4eFAPlWY1iYF3WGpKlOWsti9yWoDOr0hL4U9ZTAFS0nPalmptMeo052EsMNGdtZO2XKjYBdY6ZMsbMVDGwQ2xqA2aSt5HaA8e2YvQM/fQSqqKMsVRGWBIDz2RtotX4M8PDIUoZjnA4XXNvQJmD9UL5o35he2a0soPfkMp0zc8QIjvEVr+mdM3l+aLO9JXY+krWZqxwZDaW7UXytQ/G5v4TeSAi4c0EUSQG/UJIi5wFkkUQM+IfLQYfEMRWE2vIu7/GZ2dC1ZiCljbL/VtHmZZJQoaPSHwtk2gtrcQ/tHMyiNP9gW8UVKWN+EeQqloiUM1gVs3pi5AG5ZxHdM0PD8K+9A5B1zwFVLG7OWsDTgzE4CukeaCwrvkEZNk2Dez7JewlDQdCm5BY0wV4hJm5NvrVJdpGOWJgF20jEwhgohZjQosxseYxyRZzGsw6dOeFSAQtvhUMEe2mjliiGLwbLcgJf8AN9NQNhircYMRF6gZDILUEXiC2ZiZqvtUMspujav7qAmYA+S+gmsuzKkkseIVIC7K/RFqLk/ncDSqZX7goy9xniELmP35NZZ7SMydB8fLEYDNrgTb/D8KRgcTzVQ90zZ8A3sKMzdLqy8rA+CMGMyyByDacc4UaLjIrPapshsyvGf6XQ7DCXWb4v2kXlMuGoqHbu1BnO7A+QIXEpksZnmFgG5bAeZDzT0Sj0GxBSxbIUpHBQtAljX+Q7sV1hJm12s4hcogRAx2WwGUxcDi0FOkGy7GUCYZmFcLuFE23FheDq0BK1HAS8gbeIQbna0PLz6N2sd2GoM1ais9Am5V2UZstJoQ5xbw+gPhWqBIas6VNhHiSp2uxaZjnTRyIT1GCCq0Y2Cu2fz1NHLlX1OzVvXh3RoRT07kLtOUmc9aq2/YmiypnaP1qix3Qrf/bNgwCKcbeAVmMg9uINd2dlUE8bCiB5mvFO6q0upZVRIgDuub/INooQHFDvzuPgpTqnthJjbxGYeTF56mRG85T26XxgGhrujKY6M5TjfWC1NT8MdGML7tzdoznDSbDx6QO3zOEgm+bnM8/itdxyxMQbsN2qKr0BQ1l6o1wLcR17Dsytg3FvmPkrUzenRnIzwNacKTtAi/6iEFMxtnQEmfAutK7ZC/6A3oq2A6xADmH2PEq9h2hvxI5dnFtZepiJv0iaZz2Ck2XRfMVtpo58HcxoLHkfCs27dKIARaCm77N8GSJrS8QqCJw0hL4BKp/4zzGmTQxSO3YHJiTgeFyNWTX+H9c+qgOLPs+1ItGlsE/O7xZ6Vwvn6dWk9fDGEeV5+qcBaGOfLV1TpOd5lRo3JfUtomPB06YwSm15mC/LPQdM7Q1IYVfOFq3KKzjpi+pddzwJWcd27Oj/PZl/I6BAKu7s003AEMRNaEOYyYLTXqBdSkDwl0wlTAZzpOG7STfP7YEfFlaDMRi50hzYLy5qUNbEVitRbMRLcGarCVi06qsImjUYohK24aDbbyUQtT7GQkrH4ZWEB53kUfR7vNDPRrHM6zLBGs5OyBqLRWBr8CjsMoi1NI7pHw5VgQKwJjYhkt52QpFDPyCKqLPF8qeFGiZSSjYY8k5rnv4H/2phRZZcj6yBCgvOAIQiw+JuhmHMNz1JsI/hBkDd2OQvECCZI7MuojBGMxpDWGL1sTi5TrCGRLJsmhOkLDZ/9EKjJiDakm8gKYXUS+HQ/mfR+Nlc9YWQoKaJbY9Z3CzvqQNOIE3OJbVUnzREoTG8YGaKgQ0JFJ9wJTROY7VF2QdSHGE5kwNhc9FIobTneXkeakuoxfaRJDxALFb1goqcQtT4m5KuZt1V7Sc1zVbYXZaEVytrbhjdYau5TBEjorgRNCaJecsdjTtl5KBfzFw6CVSUlfebmnNyoyOFG82F//dopv5gag5ZNFN/6Ci5WNf46zWySfoqbJz6LHQgznfB/+4aMk557sXetkLgT3toeSmNghNx3v5GgwHDOd1N5MtdHNw8kFzYNXb4DQpB6nP7Ibme1UjFu/zf2gJnBJzPhdb77pggXlDzllLoCZrodh0schbGv5AQGM/zVXl/1lF6wPUzFHOltHAfzhHg556CspHC+sefpZU9OoFMfCmqn8Qg2B5ENw6aG8ZFBHMkEcIAEN7zs6MumRQzARYj67JYD3A2VEXDYowGJ+dFx1NBEWIQ7OLAM5jMFjCbCPARVT4HUawGaOl+IKu5T5QdkXgy85RMRZrN2B3cegMKJlNIswwAako/sR3mzk4NguD42e0p/mE72n2hp6FIp0wV8IaIAQfi8aChaApnxa7w4chCzG5ikAuhotZrSmkTS2akDkwI4MPHC0dl1j/j9g8NnCNdmtFZ2i3lncGLWu11tw0IxPmCyO4KDfqHOsfwv0w8Fwl0plzjlkC34rt3yaLW2QrFIt36X6yEy0ZRyc/J60cCZ3+jNpfcCodR//nZ6hDkMelFVtTTnPyYLH1S6CYuXVGBglWaGJNbVr8LprbzyRD3NRgKDV2FsZawBKA0NO0i4QnlJ2EJjEAI64dIGdHxNwU0ejW41QAYxHMJ5KJmD/sjY2djX0mBKNKOgM6DsyJxTC7wmAk6prPa1EXu8RgDsaZJeId2f4N5uAQMedtMdBJ3fL0tbjlcDFQnbUw6pv7T9NRexCQncnQZ5hbU46itAsrAmOPou0MIkH8TTFwEKP4OWQvcBhNZSERueUAzgWpyD7QwDuhOadpTDRaAmDXddrZrWNPkiqA/YrAp+GPLuNzJ/RGQVMmKBeHqpm+MdFvS8xN0GdC+60noSDNHJyjFXPadS2/x/WNPr2xN+gSg4thEurXWoq/0LU0JpFwXRG4jBwcC/39U7kGMLjtBIjV5N+oLr5SVbyVlFiVpQ01wTfGTYsH9AmBKcvciuGe2HTNpzgh+SR0N2aLMdpcC20mtl+EyeJFje6RhVqcL+vFYIM2aqkPQtwSIRyt/VEShvXjunWL4cus1n6jxe0L5tMPWJPYdUYM7KNrI/vAVo04Fs55leAuTGs6ngxoXct7aLCBN8ztkWnmpk8umzVvYG/XdcYceNvcfnqaWfN2RfGnunWDSFWf6db1xS9ow9v1Ud/7/Wnme/9Geswd29e89kOYr6MmYEoUSN5dpsVpLA1oxIhhTkvdkWxBvUzGOFHxzC/JS87mbSce+/VAg9QQ+Btm6VyC8QZiTdcxUWe5ZAEZfyF2fQv6XOURA2fNXZ+Jms9lmdu//oGoeVV0vIrrNWLObjHwBVj8tIc+IrDmCzEwPExGjA99m1fcB0auPyYu9pmoe/4L0G7jz/mK2gwHxK6voKLVP0fNr18BfG5/ZYFR2Ba8EwY7p+HPVlzBDI04pVx+MZKJROMpHJEks4CsNRcf1TUXYnXBMeglnTTCfswHvT2hMijU2U7ic1Gc8v2vVj6ZlCerYIbzoVQkEUw9Ol0PpYwhMfjUZs8SOuz6IdjYmn8pAhUcgAoeLSsLHycVtWnQuNb/Brrz7UuqQNbT8OeludUgK67+hvLD8ICR/22YkH8wDvl/7yuT79RQ8heR9VhzN0W+1T32ExpIiTnXoE0+FKmv/gAi6uReGFFbsI3CD5Merhy9P5M6na5F/AbmKbO/oWGDf+DCB/exZbJawl8yfN2GkTJSmafbdpYwH+r8BLN0hLwhyH9jMpO8N2HlsXdJhA4BNxv+OELQtT6XBhEk51NLcHK7PMQk9hSVRrf2aVl5vY9bikO6x57EUVLOCd3a36KVM2trtQOhOcGUMIRV3dr/JE++oU9mw5NZwckfkEnyC8RlLpp1z+8RW17TrT1E+Nktdh016ywwuPpW7HpfDFwSdRXvx3hAY/1CLN6tW3+IjEVf063HusOzoCUtGsJV64/RgnMXQqtuhT8vDf8RtCqu4YfuBnUAl2/s/gqUvz0VGduFjMnMBqowlj30Dc3wS5JhJ2aQeW6xQAbDa50S6v2zTxLq3XuS6v0SpOFfEedDaTjpWiKiznxGlIega5i379atW0OadQ/x+L0JPL4dYyBEulHU4feQ9Q6y8ilPC8XWasBArC8KvXgj1r8bh9mlYuAc6PsN0FtjsYXwBNxALO3CcABRRFdxrJuud60ug/yrdeGTl4jwJTQ7V7zlPAhzWSkMdNa7SP0P9An/5yXa7xT1QK7XxfbL0x46SQV7naoz6yTxwG+ndvfALObgvlTwvs4h2C4LTiZslyMf03axnSBDsgwyhjP6inDQFfEPjo6EfnMCO7Cu0P85QRcF6kIanO0/tBMXmReV3l26uPSeUmnxDnkNsu+aB7SCPzXU9yQdzCF9SrO98w/bp1eAKc7A9baqOWCKPyLjC+Bk+0hcafgEv8WyvFsJWXBbMPQcPvjdXHgwmyzCfGhoC31NGKJTmG04/Asd+pjDPI+FcfslVHqCRg0YVJGVuKFcFdsr5CpmY2ESVnC+KU/2QMOtk1PEhzoQDL6Qsg+Sptc1oSkgXedNqOIdH8UqFQMwLno1tA9I7QYrvE0xkdyKfVvoBZSEcPv0R2R9Dlf89NjVZuCsPpOtz+thONCcdZzMvNr8g9CUsQ8lqzKhNVCycz4yuY9NJzEAmIvblo815+wheQy4xqcFwTvHbb8fVLbtZzhb/xL+bP0G6IQWY+VcXnOgLfQusGb8i4Ywi5L1PoHzx214ImUrHoNG3PwTMvtHPmRruc+wuegzCSeT8uJ5MxnVwRCnafeg6PJAE+o9NuYZw+anTRcG6n7yG2B1ewQMJfTAh3K9NlZvh3DhrtgqAzWAdz7kDOAomMtW3E8MGUkT3Z2lJ9P8hGrWtRB1KlQ9GCiGncgGqeDkB4krv4uvfAlqGjc/Qzs+7GHlD3er/CmoLTwLK48Z7KW5ssE+DU+3/wqsPLQEv82bD1l88Oelo/Bn62Vs5RUf0FUnlZnoHnmETI44U3kf5aR7WXGy/5c6+3OYnTRfIS/1H9GbcEs51Hoch7uk2VseT1ZIMGiu7PiHjnc3wmps6NiiyISPyJgTl4tX4ZD6GESkAR+gXYbpMga3VIILM8Xv+n+sy0iGOWGnW0364gcK0oc/7E76xeOE9O81cUnrWu6EB5R8+EckTwUZqOhxJQa/ZJI18e4N3X15PLWsENDRRaX+lkIW0APrUng/agTvw7UdahXNWTigpjOLPsfp+hfmWggCYSucJfH0OG0SrDE06BgIHZs/n/iACp1iONI5C6KPcv68HRcrQh8ck0f0dFpbBkrIwQFoKl0yDZRpcZjPdq3oRDtwjxZzjKRD1GHKef2SY7QrWHgM1x/S6haBKRgXoR2b6Yp6BDn+J3TZla/QpVBwrbrcdjSBLluOcbrc875Cl784fnVd/uzod6zLQUepLvsdJbrcB2Fo26a7OF3++ZiiD91QLceLHwP3oRYoFlqDNIIwH6/URsPwe+8pnONvx6hsN8rritQ/ngQaJkOks9Yc6KCL8r3kJUp0PS1zPZ05oJMXKc2BmRnyqiN8116xo+iYyRbCZ2ZTOK17nP0cOCVrNxNwNzF4cw977OBRucce8F63HnvE+z0K0uqOuOsI0JwcryO+QREuHwTynYPU8cjxvkLls45Sld/AxaPR75El3AXx4pys7P7/jOf8bbzCc3aPv1bPaT6SwHNmv8d5zvrDCs+R3r+65yw68h17zuHD1HMOHE7gOSvfw859J242kJHv7yEj4ReNZjiWTkh7NaO9/DAdLN8DpP6sCf+OMLXTcCT8b/RbtGn7hGZD1s5kgkudlKtoBWPutbbC5XcTtMKuw1wraN9lVSKLLx9BFokjkdXMppm45WQOTjO3zmRSbXoXpYmENkLafMTXPzwJMjYf0bWM19AtnU1sS6cFV6bCT8KfToHX4LJ3OQ0ePkQ0qGvukLc1dS2vEIF5TRa+SzU5FlK11vy6zpt4JaaH0lCiXp1JnV6qyM/GKhTZNfZaFfmXQwkUuepdTpHb3+EU6WFtXgJFwx+kMo75qLnkEM2ReYgeyoiqjWw0SGRpbmf4t6kxYS3FXb4RoWzI33kjj4P4Dzhj82lff1RpxzsxG/pijEL0b8Zcq+hb30kg+kOHONF3HgQpi7G5B5NDRjtJ+6J0Xx/EiWQZNuvvUpAHbs/unnfo+syCd7jNy/CaFLbIGD6hidHCfM8dVGjKN5XuiE5SEO3NiGoY45tYb9KZwZOyMVIbGamxlNQoBaltBympFw9SUhvl0zlQ8KkrFWxhBR9gBZ/iCrKzN+Rgl5Yd7CJu0cAKiazQ2mihu+kZmJx4G8DDWKmBB6kOGwX5cNPyZHYaRtdyL35VnIj56G16IubI29yJGFyRfhqN5w60vAtJ1PJwFcBvYFPlIuSVdCdFaxrJjL74IF3zLgo9BrQ6taTpiPGVZxnFJmMm1P9BEl26MzICqSHb27SUMdzGqolm9w9XZi2Ss4ZyyTcLLvSVslX50kx/g7z2Z4FJpKX4C18pWxnNpkF5pDKUhN+ioeSDt9TLqv4ObhWRLui/gplA/wR4ngBltGbCBlQP00NNbF2yZyzUMhbu6QkLxW+xPYXwUoU7nAn96k10rVVZeYKupQpjxv00AwmnT8XCaWu3cHriTcrA+5B23sfTnA2YcJpGbnksfoEVp8dy/sCK/hozvi/EKtwfq3C3skL/3s5/0B4AmNUKPj+VkbS149o0N5bVnvVmDzQXOSDvxnx1gK71iHiskBDF72Bg7DAhob3vAPWkPQdktYJzB/FYFimkp9+hULTEL1kFeaEnDsjLYF8zP5oHzVa7IXb8sulTiD9d5sBlbmzneovu7d8DfMROaZHONyjQHch/2U9HHwGisQu65SNwIQbFgwHk5TfJ9iQOhojsMBrCjbqR5qZvNP7+pY/2Kl1rEjoHwnAq14JHMS7jaYyX9sur5ThWCval57SUByfNgRFi086M6DreDroQdw9hZnc0iI7YT3uwWuCDnjfA87AgoxiUjNgMvehhowJz8J4ihKtpBKtQRLCF+6neK5F6xwyyc915uyLLBJZlHM1ipMtHhKb/T/Alj6tsPMB6hCtpgDVHA6yOUflkH6Gij1PR3/fRLDtpljxWEdLzb4YvGVxFWvm0roLCo4zCw5QCO61FM9ZuqMLl+o5eZPrS1KENWegR1lA5tb1F4dn7+C2kbvmHs/yD5Pw3KfNH7c0SnAZ25PsXGMCBl/mgTWBOVBF0g491+kd2zmTnJdBSD72h8qX3faMswVvRks7QLUz/J4rty72hZ9/A/X86y6K+9q9v0EFh8A0yjEZiMeuJMdhN/giTowzaRndzt+dj6fNQ1n6Wb8wbCnnn8w4GMSRXDOaLLectAWdWhq55PXQtpeRAn/lleSnRZPjYZGjbQnYUp2wwnDa3lmlE3O9p0z1mItubYUvOa5bA55acA5ZAm5gTqgicNAfeqghcMAe+wtX3ltd0zZNIp9UBVa3sQzbQocd9cKDhNUhW9sVNwl+1E38g9eCOre75dosmhMv+l2H6Yg60W3TPv17R8lrjODHwBt1pvIjbC11H4NtRS+AQ21roWD0Fcq0eED6noec15CxcMcWuwiUoo1u3Q4MsvdZ4M4pn6b3HUhxarQ/bNfzZdtyfnN2aMhR3hNbNIgU+9i03B/ZW6J5/q6LlQGN+rA5L4ATZnfkI95p47syQcbUujN0P0qP5YuWApFln/rTbLg6wqCc1HtCt/SM5eXOAcrrPUnxW99grAjuIcfdlNCtyigQk/odZ9/wZ6Bwai7gaApfMXUcs8FdXAcnZKGezIOPqwWHcTo7JTHPz/EUqdOZjPH9mpsI19Exc4wjD6YrAF+QoS/iNbyMRUNkwZLJ1EZhT52B4Zm5NyQX7IVl0rS9/m2BvTfg7WSXBHfZf0Ol610W2Hy+ObBc1+3HLqmlnJrd7EneXect/o6uw3x+A+ZsD76AHWFpH1d6sF+aLreNckFaVBr41B85bck6Q30q1f5sc6thLJ6t6w5HY+ZOvLYHz5YEzpZFB74H3a8Ti9/2nSLxaHHXfDTH9fbGD/faK/NqK/t52fI19+Xivr8bhEjxj8JfSwvg6d719vMvxY8f4eofLYXO7aqwF4+2u5d7xVp/NXWP34Puyxjes9NW5XQW5ReO9Dp99XIPVdq91md1L8B6riz132Mb7fQ6nd7y3zuqx10gee21uXUODUOb2O2tct/n0+Htvfa3DadcL1frbs60ut2tlvdvv1bus9XYvULXnlJTItEpKCLGSkhi1ycB7SQn7KXtJCf9T9sn4K/ap+qklJVCJx+pze8ZNzc7Rk7dY6BdV66for1Z2MfA0+jp4umoRfFcKFJFQcI6/25XsXROZxQLPf0kJfQHDdQpwLUq9/Vp1OspbopekBrdXn72izmGr0zu8+lH3+3P0U/W+Ood33FSv4347EFU+Fczj5+ppnQ63Sw//k9/41xDj+WdsZ7ndBlJMdrpdy8ZS7tkLYxgShL2qDfWAxmKBZiopYS8vERyu5Vano0bvBP/xWJ36WrdHj5mB/gqHr06PLynRG/JKbvsOpOupKUFLdRPgGspeg67+5zhaLOj7wP/9e6s8hH+jjd7ldzr1LrdPT9pEldPrXwpfhRkYpjAPDVrQXB67FSLnMiFPP3mK3qUfPRr+TNbXWH1W2Yq/83BKRIMiXh8JpAiiDvSImVw9Fc2r1u6xu2z2HscPUpSYaazpFi3ORkwObTj8uljIhs9S/dQp+rwc/TSgjkKTlnH56+0e0JfTUe/weSfX2G1OJJ29NAco1lsbwQrG6Zfm6Ev02T3I73DR/EjemgMf1Ost7uV2T63TvUJvq7Pb7r3lO9erLLg03lpTQ1SLQl9dh9FyYKA1Ndk0BBDVXafb9rTVPNYVktXjsa6UI0xiv7tOkoupXTtQ/w6wa9J2y+y+yXlTsyXguMH+3Zu3w2Vz+mvszMyBGLJDmgPMBHs0u8unx4dTeywVI8Kic09LNRABu+s26hhUv6NjDjJW31B1DcrmK0DfWqqfAp6lX7UKPet2PXU0VD0Nfku92daca/G48bGCS8GHYnQnx6E7tUd0iWcq6f6Pe2e933l93gkFFd5Jo9nk6wlmY64xmI353wtm0HVdn7qgoEJd+P5EQ7400zJ3eqlFkuZIhiK53ARi0ZPMc0345ivTVfIZJppcyx0et6seXLlnJQqqfFb04poeZS82ya/Nujrh6TDG4rKz95iw9/vccJdR8V4fGR/+EcWL7LmM38rwS1T4tQzfqMIvYfgNdynf/7iJwbiJSVKRpur3U4qqfBtU+a4ifN4Cq9NvZyrl+cpYpOQ3+h6URcr61piV9WluSr7jCfZuHOMrkQjuNK3ZHoksTBKEzZDintVxSN/Dd4a0RSK40bsZ0g3wvLI9EsHNhH2nIpFByYLQ1hmJjIXnxz+NRHAvM+N0JLIKUiOkTyEe0rdwfeYzqAfSPEj7Qfm8c5Afym+EdBN76ZH8jh3N/fMETWOG5qZ+vbQbNL0yMth7ai5si0Tk96XEz0vfA4R5v4G88juWstj7pcSXIxEj1pWeMSM9c5au7wrtGmHasDtuL8i6RX5f6UKmC/n9SVgOX1O9DuQdgXJMT88oTc8sTdc3Ja9PSjqNXzOmp2sBYZe/464/7mI1gm7Ie2gA3ZQkpWvZ+3xw4WVdnGe4KIuHGDbCsycFWtf09Mzp6frp6dml6XlNaetSW1PWJz+WlNScnk3QmSSLltIdBPylQDv8IEr3zmidefBM+2n3OkVyKBx0Bs9wL0oo5eqcnp5Xml5Unl7Z1GtdWmvq+pTHkh9JSt6dlF4E3EznWChFBVRim2Cb6/8WiYxk9WAt0fep319pIa3VKxlfsZost9lY1kaZ0Gb/iu+6MkpGlZ7ncnoWcButGv0V8q+GiJdSCfm78z0z/WxvBeP2IfEZP9ub6gE3MV/4JBI5hTy8sMSo1n95upFrgv+LlShaoTQ99p71jaDLPWD7dtaOjyVBtvXJpnR9awpQW5cqpuc9kiamFzX1qkg3eghjKnLEHkNA5+zpmC3jJxLR9EMHGKS9Uxi+gsBHkwT8mcl7moGts4QDSf1fNQu/0/bfP1d4QXufIDzbO3VrpfB8n4xnK4UP+/T/qFLY10+3xSJ803/weVF4PP0SUF83YGDwh8LfBw4K/FA4PhDoCdsGp34+V3h5mHaLWTg8PPV3FcKx4Rt7QXW39vvCIhzN6veiRXh49Bj4/nX2GPi+/vbnk9oswvZxk86JwvlxA6HY2tz/0FyaKfxpfIkgnBxv3T1T2Js38vBMoTMPItlmQ0FwpvCRASTpMgz8YoYQyL9xzQxhf36fkEk4kj9UEL7MH3jZJDxScOM3JuH1gj7vmoTzBX2A7F8K0yHLx4XpgOkqTAUOvim8EWi9PGEA4J+cOADwu4r6BEzC88UDt80UHr+jz09MwqU78PtvJ6cCr3+cnAqs/nVyfyj13pSBfygXNk695a9lwpmp4m/KhP8u7dMxXfjL9IG/KBM6pv81g+p8UJXugEZYWgsNq+kD3w5oMoXvP99/vv98//n+8/3n+8/3n+8/33++/3xHn4zhbF2D3Qt2/Cbj90r5/+ijSZDuTVPCb6ngcwyW3xm96Uba7vK7orMqKCy/A1m+N0x+x7H8Lmj5XchF7Lm8DiG/6/qryxE3pk8lUXryu7T3aCksrwFdYM/ld16fYC/Rlt91LU8DB6vkj77Lm71vWZ7D70lRrmHJ7+SW3wF9fKBRgT87wKjg+yxLe6vqvxyh8uSx/BEGy3ycZfBzGf+7fhS9x071Ocja+SRLz7M0LZOmQ1g6mqUTWTqDpQtYWsvS5Sx9hKVPsvS3LH2RpbtZepClJ1l6nqVp7B6iISwdzdKJLJ3B0gUsrWXpcpY+wtInWfpblr7I0t0sPcjSkyw9z9I0tm47hKWjWTqRpTNYuoCltSxdztJHWPokS3/L0hdZupulB1l6kqXnh8W3k5llZSX67PlL/S6fX1+UW5ibN87gJ5BhtaEoN68wh2IFm9PqWqZfbvd48SiIIS8X/htXqMiam6+/oq0kQ1SQ72dU4pOi9xoq8cmCLy4+JernSnxq1L+V+LRoHFDie8X1n2TwTtnvlPjeUf9V4vtE/VyJ7xuNd0p8P6EtLr5/tH9U4tOjcVKJ1wl5cfEZ0fselfgBQubd8fADBVym7Y6/IRqPlfhB0TisxMfu/1Lih8SNE8kQJeX7JJT4zGicVeKHCpvvi4eP3f+lxN/UDTdDwPsXzkXi92/d9XADw1eq8KMYHpeW+c8k0jfE2lF+N76F4eX9G/md9g8wvLyPJOP/L8PL+z7yO/xPMHwlPdMtnJL7SQ3FG2dS/AjWAZcw/BIV/WUM38bwTzI8vlxIA/o84Fmi6MdPsPz72DhuNXs5flkSzb9flX8eweui+1dyv/Yww8v7aDL+LwzfqMKHGH6DCj8imeI3qfCzGH6JCt/I8PI+m/xO/k0ML+87yneaHGF4eX9RxqenULy8vyjfUVLO8PL+onzXQAPDy/uX8t0Bv2T4hYuU+V9n+NBdSrwmleLbVPhxqfHtuSiVtleDKp6UMPxGFb6C4dXjclsqbd99qvb1EHz3OPALRic63mefZ0n+7vEkEf87Sf4BwuQ4cSle/gOpdLSojnsnCJ3u8eezVOrdav4jDK/mc2Aa0ukel7IT3Od4RwJ8NblrZ2i3eLUoLf79if4EdPb1xfs4usfDvQnynyL0Y/2FfAfNxQT5+5N7J/sLeawd/1XWQ4L7KCcluhc1AX4L4AckDRW2qPjflSD/J73i3/84Uhs//+QE+DsT4B9KgD+jQ3z3/vfXmD8J4irzF3k+sDUBnX8kwOf2jo8XE+DvToB/qy9rL8aPvLfenCD/Uwnwf+wd/77O/Qnyf9Q7/r2i0/tj/u7jn4I+tN3V9j+tT3z6zyTA/yMBPqtvAvtMgDcnwLv6xr9XtKVv/PtStyag83pf6u9qP/06FfHDhEMeJf5IAjpnEuD796N01Poc2i9+fksC/KYE+H8kwI/uHx9f1J/aIV5ngR+7bM8J8j+VAP/HBPje6fHxdQnwD6THvwf2lwnyX06An6mLj5d0VF79cOU6w8oE+R9PgD8h06lQxpOvEuQfkhEfPyEj/r29VRnx7wtemoH3NEF7sXHmBVbx7zPi38/7ekb8+3/PZcS/t3fKgAT3Xw9IcA8vXgpI72CUfNalTruhGya/G6ZAiJ658vqXSmapJtfW0ICXJfb4NFZ5Hr3C81rOrl1XmfwelCnw+jxl+SZ2k+YVsxbiTzF6RFQ+K3g1rsnpaENe7HS0uco3kf6AwDynKk+KsYiXVFZNkEwm01UYKFrqdzh9Dpe3cI7bZadXqBoMksTOUEo1hXgppM1pvrpaoDJkopDcfFwtmQwGj93rd/rI7cimuVWTJHLnpqVIkhxuvAyZ3DR7LafyepBffYSxJ0VUxyl7UCTOmc2rl4qdCL163mKlCFXXqKWqa9dS1bVrqeq6tFR1DVqquiYtLbhGLS24di0t6CnzNo/P6/PX1ubahBq7x77M4fXZPZKvXrI5wc+8giTVuKVlTvdSq1OqAf/1SlZ/o2Bz1zc47T57Te6k4uJJ8TNJteA79HcJEijWs1Ko9Vjr7VKNv75+JRThIHLluCKrJM2YV1phkkxzyvHqdGnmnPmSSWRIsXyeIJX/aE5phbkMnikK1ygR5L7YaGifO2NGlalaqi6dbjFJ9Lpao5G/3ZW7SZ09YLfBSnb8dZDi7mFVhu/gxmUFRbyPtvtN3KpKzXMl8iNQye+117CbdZUSkatyE12objRyd+Fe8U7270pY7iLi7tJKNV63VAfe67THvZdYzUT1AqgrduOz3Vqf4MZnk6okf0NxHAOQL0dW15f4tmo1/e5XQStVXeOEXpG1BpioD0g1OOzsGuQYR4bC7/xO+jhaj93DrNYFNkH3lndjS0JPDBo0O02meVXualVjFrObnNX0XCvq4xhSnEu+lbnwAmg1qX/qAvY4SqiuKJODDbua3k3JyJLGM6t5yHysaqwUokueZKqaKFXOriqQnGq90NvUJ9jI2MNmgsapkFY4auwuErRUguPV1dd3JXw+/yNJU72tm8Dkwm6lTtFe1VqmmqAWv9RaI9msXl8ctyDXk3f3zjmGPMK4daljuQFDi9cB3Qr4HhlpgcS1bpPCL+jF3yomJIy8LJDT28S7u6xvIjoTjGK72Y4kLYX6WDeAEa5QlgdYlty1Egwel9ml2nofuPH9Kj3lsfa6Zv0X1OI16bUOjxfrIMH9atG90AwGUNad/+tq/zxof4+9wWm12U319XH7FryRXa1pcsW6zeuX2Kj3OqqexH4mbYpTI17/HqftVP4POpg3+zpqNsVT8PU03kTSeGCnPgm6nsTtx+6nVytxWWOj1GD3eN0uq9PhWyktz1N1s9fF1CTOoq7IFVEpi4dgW3Hj1gSb0271YOeQTzoH+AedkD1eL8aGOioBFDOvgoq55TYnzt7mu1Ygl/NgOlWP1GCOXZCbd/3DBRuEVJ/dNC+emDFjxXEmE9vOz5HV4pACJBJIOCrq1qOYeQLqwsvq3S5WWOqugknQtYLTLIf5p9OpnF5id6CeYRZIc2EAxEwhVmfhijqrr3sAQMZUPhIn1nIansBrOMGQKLHPQCd95WFXt6jVPeoKud6V9T7rUkghYpO0Tv7mcMEMo0HIBfr2XDCqcT7rMgYtc/lzcZ5fM85RIxCozuqtE3JrVrqAHk19HvqEHSNQABI8g3GVFTOybw1OH1YJ4SwXhjjwl1hLrsdNxvO59jo2D6mr8cQgIGqzKZaHKA06qaA05O9IB6sCkoRBa73DBuXdPvKH1k/rgo5IyIWZE04zv4tzMzexPR55nU8+F1HEEMMTnL+SP7eyM0Vyefn8RDVD6LvtmSk/BlV5+ZyFjyGyrlIefxd1PhJxy+Xl8xhPMcTdDJ+qOqclf+awM1dJqnNZ8vrjPlYwjcmuVZ2PWsDOQiWpznnt0SrPdSXS3z3sTJVcXj4H8hxbMF2l4j9Jld7LzmjJsHxeJG8AhduEGP/JceS/n+k0SXUu7OwA5bkwtf5k+ZtZ+emqc2bHByrPpaWyMury65lO0lTn8jbdqDy/lqj9A6ry8nmWNlbQmKw6/6lKn1CVj557YUc2bsmPX17+PK0qL+/PZVUoz9Ml4n+jyv/kfdE8Vr4yXZlf3X6bVOXlfec1i2LyXan+F1Xl5XM5mcxxspOvXH+bqrx8bsUoUXid5sr1491F6dx5Qnm/O9sZX99aVYpX6Oq48vI+epEzPr/q8qcY/3J5ed/byMpvUvGvjmddnG/x5xBD9UpHTVPVm8EFBL5++RxSyN0z+VNV5aPnAhposllz5fLpqvLy/uDm+65cv/zB3wdrufLy/l8bK595Ff0NZfXnqe2Kla/swfnfpDj9WoaHtSfzHzy3NCtO/OnN6477VLKNo6YBV47fAxKUf/NxFj80Vy7//wBtIfjTuJoAAA=='
    bin = gzip.decompress(base64.b64decode(gz))
    with open(pymain, "wb") as f:
        f.write(bin)
    os.chmod(pymain, 0o775)

Submission status: Accepted

Solution code:
max_n=10**6
mod=10**9+7

frac=[1]
for i in range(1,max_n+1):
  frac.append((frac[-1]*i)%mod)

inv=[1,1]
inv_frac=[1,1]
for i in range(2,max_n):
  inv.append((mod-inv[mod%i]*(mod//i))%mod)
  inv_frac.append((inv_frac[-1]*inv[-1])%mod)
  
def perm(m,n):
  if m<n:
    return 0
  if m==1:
    return 1
  return (frac[m]*inv_frac[m-n])%mod

def comb(m,n):
  if m<n:
    return 0
  if m==1:
    return 1
  return (frac[m]*inv_frac[n]*inv_frac[m-n])%mod

x,y=map(int,input().split())
if (x+y)%3:
  print(0)
else:
  s=(x+y)//3
  t=(s-x+y)//2
  if t<0 or t>s:
    print(0)
  else:
    print(comb(s,t))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    X,Y=MI()
    N3=X+Y
    
    if N3%3!=0:
        print(0)
        exit()
        
    N=N3//3
    a=0
    b=0
    for i in range(N+1):
        if 2*i + (N-i) == X:
            a=i
            b=N-i
            break
        
    if a==0 and b==0:
        print(0)
        exit()

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]

    for i in range(2, N + 5):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
        
    ans=fact[N]*factinv[a]*factinv[b]
    print(ans%mod)
    

main()

Submission status: Accepted

Solution code:
import math
X, Y = map(int, input().split())
if X > Y:
  X, Y = Y, X

if ((2*X-Y) % 3 != 0) or (2*X-Y < 0):
  print(0)
  exit()
A = (2*X-Y)//3
B = Y-X+A
N = A+B
nu = 1
de = 1
for i in range(B+1, N+1):
  nu = (nu * i) % (10 ** 9 + 7)
for i in range(1, A+1):
  de = (de * i) % (10 ** 9 + 7)
  
print((nu * pow(de, -1, 10 ** 9 + 7) ) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
def cmb(n,r):
    if (n-r)<r: r=n-r
    if r==0: return 1
    if r==1: return n

    numerator = [n-r + k+1 for k in range(r)]
    denominator = [k+1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p-1]
        if pivot>1:
            offset = (n-r)%p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

x,y = map(int,input().split())

MOD = 10**9+7
n = (x+y)//3
a = x-n
b = y-n

if (x+y)%3 != 0 or a < 0 or b < 0:
    print(0)
else:
    a = x-n
    b = y-n
    print(cmb(a+b,b)%MOD)

Submission status: Accepted

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p


fact = [1, 1]  # n! mod p
factinv = [1, 1]  # (n!)^(-1) mod p
tmp = [0, 1]  # factinv 計算用


def main():
    x, y = LI()
    ans = 0
    if x > 2 * y or x < 0.5 * y or (x + y) % 3 != 0:
        print(0)
        return
    n, m = map(int, [(2 * y - x) / 3, (2 * x - y) / 3])

    for i in range(2, n + m + 1):
        fact.append((fact[-1] * i) % mod)
        tmp.append((-tmp[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * tmp[-1]) % mod)

    print(cmb(n+m, n, mod))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

mod = 10**9+7 #出力の制限
N = 10**6
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 )

def knight(x, y):
    s = (0, 0)
    if x == y == 0:
        return 0
    if (x + y) % 3:
        return 0
    if (2*y-x)%3 or (2*x-y)%3:
        return 0
    
    a, b = (2*y-x)//3, (2*x-y)//3
    n = (x+y)//3
    r = min(a, b)

    if a<0 or b<0:
        return 0
    
    return cmb(n, r, mod)

print(knight(x,y))

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())

if (X+Y)%3 != 0 or X*2 < Y or Y*2 < X:
    print(0)
    exit()

n = (2*X - Y) // 3
m = (2*Y - X) // 3

P = 10 ** 9 + 7
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N+1):
    fact.append((fact[-1]*i)%P)
    inv.append((-inv[P%i] * (P // i)) %P)
    factinv.append((factinv[-1] * inv[-1])%P)
print(fact[n+m]*factinv[n]*factinv[m]%P)

Submission status: Accepted

Solution code:
def binom(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)

    res = factinv[r] % p
    for i in range(r):
        res = res * (n - i) % p

    return fact[n] * factinv[r] * factinv[n-r] % p

X, Y = list(map(int, input().split()))

p = 10 ** 9 + 7

if X % 3 == 2 * Y % 3 and 2 * X % 3 == Y % 3:
    a = (2 * X - Y) // 3
    b = (2 * Y - X) // 3

    if a >= 0 and b >= 0:
        fact = [1, 1]
        factinv = [1, 1]
        inv = [0, 1]
        
        for i in range(2, a + b + 1):
            fact.append((fact[-1] * i) % p)
            inv.append((-inv[p % i] * (p // i)) % p)
            factinv.append((factinv[-1] * inv[-1]) % p)

        print(binom(a + b, a))
    else:
        print(0)
else:
    print(0)

Submission status: Accepted

Solution code:
X,Y = map(int, input().split())
mod = 10**9 + 7

def nCk(n,k,p):
    fact    = [1,1] + [0]*(n-1)
    inv     = [0,1] + [0]*(n-1)
    factinv = [1,1] + [0]*(n-1)
    
    for i in range(2, n+1):
        fact[i] = i * fact[i-1] % p
        inv[i] = - inv[p % i] * (p // i) % p
        factinv[i] = factinv[i-1] * inv[i] % p
    
    return fact[n] * factinv[k] * factinv[n-k] % p

ans = 0
if (X + Y) % 3 == 0 and X <= 2*Y and Y <= 2*X:
    a = (2*Y - X) // 3
    b = (2*X - Y) // 3
    ans = nCk(a+b, a, mod)
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def nCk(n,k,p):
    global mod
    k = min(k, n-k)
    
    X = 1
    for i in range(k):
        X = X * (n - i) % p
        X = X * pow(i + 1, p - 2, p) % p
    return X

X,Y = map(int, input().split())

ans = 0
if X <= 2*Y and Y <= 2*X and (X + Y) % 3 == 0:
    a = (2*Y-X) // 3
    b = (2*X-Y) // 3
    ans = nCk(a + b, b, mod)
print(ans)

Submission status: Accepted

Solution code:
def ext_gcd(a, b):
    def _ext_gcd(a, b):
        xs = [1, 0]
        ys = [0, 1]
        sign = 1
        while b != 0:
            q, r = a//b, a%b
            a, b = b, r
            xtmp, ytmp = xs[1], ys[1]
            xs[1], ys[1] = q*xs[1]+xs[0], q*ys[1]+ys[0]
            xs[0], ys[0] = xtmp, ytmp
            sign = -sign
        return (a, (sign*xs[0], -sign*ys[0]))
    if a < b:
        d, (y, x) = _ext_gcd(b, a)
        return (d, (x, y))
    return _ext_gcd(a, b) 

if __name__ == "__main__":
    X, Y = map(int,input().split())
    if (2*Y-X) % 3 != 0 or (2*X-Y) % 3 != 0:
        print(0)
        exit(0)
    a, b = (2*Y-X)//3, (2*X-Y)//3
    if a < 0 or b < 0:
        print(0)
        exit(0)
    n = 1
    k = 1
    l = 1
    mod = 10**9+7
    for i in range(2, a+b+1):
        n = (n*i) % mod
        if i <= a:
            k = (k*i) % mod
        if i <= b:
            l = (l*i) % mod
    _, (k, _) = ext_gcd(k, mod)
    _, (l, _) = ext_gcd(l, mod)
    print(n*k*l % mod)

Submission status: Accepted

Solution code:
class common_function():
    """
        1. よく使いそうで予め用意してあるものをまとめた
        2. よく使いそうな関数群をまとめた
    """
    def __init__(self):
        """
            1. 英字の一覧をリストに格納しておいた変数
        """
        self.sletter = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
        self.bletter = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']


    def combi(self, n:int, k:int, MOD=pow(10, 9) + 7):
        """
            mod の下での combination nCk を高速に求めるメソッド
            n が大きい場合(10^6)に使用する. 
            1回 nCk を求めるのに O(k) かかる.
        """
        k = min(k, n-k)
        numer = 1
        for i in range(n, n-k, -1):
            numer *= i
            numer %= MOD
        denom = 1
        for j in range(k, 0, -1):
            denom *= j
            denom %= MOD
        return (numer*(pow(denom, MOD-2, MOD)))%MOD


def main():
    common = common_function()
    X, Y = map(int, input().split())
    if X <= 0 or Y <= 0 or (X + Y) % 3 != 0:
        print(0)
        return
    if Y > 2*X or X > 2*Y:
        print(0)
        return
    for i in range(X):
        two = i
        one = X-2*i
        if two + one*2 == Y:
            break
    ans = common.combi(two+one, one)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] 
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

X,Y=map(int,input().split())

wa = X+Y
if (wa)%3!=0 or not (wa//3 <= X <= wa-wa//3):
    print(0)
else:
    MOD = 10**9 + 7
    fac, ifac = make_tables(MOD, wa // 3)
    ans = cmb(wa // 3, X - wa // 3, MOD, fac, ifac)
    print(ans)

Submission status: Accepted

Solution code:
def com(n,r,m):
 f=[1,1]
 for i in range(2,n+1):
  f.append(f[i-1]*i%m)
 return f[n]*pow(f[r]*f[n-r]%m,m-2,m)%m
 
mod=10**9+7
x,y=map(int,input().split())
z=(x+y)//3
if (x+y)%3 or abs(x-y)>z:
 ans=0
else:
    ans=com(z,x-z,mod)
print(ans)