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

gz = b'H4sIAEMB0F0C/+19C3gUVbZudTqPBkK6QdTwkoBBggwhnQRIdNSEpKFaOhAJID6wSDodEu2k86WrMfjESeLYNlGOx+s4zpwZ7sxcRz0zZ/AxDHpGCILEx4iIiCgiERGrCQqoQEShz1p77+rsqq6KMDP3ft/9vmklu9dfa++91tprr/2o6tr3ujyzkywWQf0kCVcLSD07uoTQJQx/wBtnAaxIGAR/xwljhFSgUzi+EqFEk/axotXUxvis8C8Z/hUlUbooqUSTjmF8amrh0hSB/5RoUtv1giYVhKx4PpR1z1KK7lm6TJM6kimel6bNl8Ty9bF8fYxfTYUkQZOq+iWzfwsZvpDppabljK+c48dP5WdyLbHLdcwu15Vo0rsY3126fNdBvlTh3D8Oli5g9ZnZJYfJr6ZqO0zzN9TMKJzmr53qb2gKtU5tLZoxdUZhbjCQm09kcjDeOfMWaeyYyWQewXwAr5+xV/zp+p8cv+vsjzemT5p344y7jjt78Foxy4dN0tHkqE8ePyjJIhQKq6BovPZj+FcK/577qOC9wfetkf7D+/KrDzXGXnugw3vRrqq1batvKDk+9bh0S0bWirwc13uersOXdY14PL3sV2OaN6x037Z+IPscBAGGG+DvJhnj0yzG+HOCMe6Ie5j2M84EfzvFuJy7TfA3TertNOEXU43xNBP8ehP8p8nGeINJvZeZlFNkYuc/m+AjTcopMLHncpNyGkzK+cqEf5wJ/3yTev/dpF1STPxnoUm9L5nwDzWRZ5kJ/3wT/pMm/j/epJwnTdr9RRP8JZPy7zGxT4OJPQtM5F9pYrcRJvz/ZaJXo4mcpSblHDGRv9iknI9N7COb4G+YyPmlSf+aZGKHnSblbzeR8woTfV82qfdSKGe8MEpYV0PHkUyGD2f4Me8yzTg0KYXiQi3FlzB8SDLDWTmrGP5/WL1rRpZo6p3D7LNslBafC/UOg3J6WPmqL92RTHHBt0wzvn1gofWuqtHy25k983T1VqbQctbWaMu5ipXfw3AHuzCH6bWsVqcXs/8xnfwCjLdBudY7ZQqOsTMESVreGGiSgnJ1iyxJgnTtCmmBb3lDUPa1lPmrg0FfUJDcCyukWl8LgxdWlPkDTb6F1TV+H71mfEVqlutbfNW10m2+lZIXvskIelurpboWn0/ytXp9zXJDoEmQbpxXFSyEapudeRLWFJRbAitdC+ZWVbu9LnI5UAwXGpqCvhbZ7Xe5FlQFFkp4YW6VPN0rr2z2AaOzAHhub6j1NQFng+xaAQxVsnOmJIEcgdulGhCl2u8PeFfQnEFnQV1DU61U19ASlKVAnatyrrexkVY3vc4fCtarRczgi/BWB2VSAlwoaAk1yQ2NoExLS6Cl3MllCIASvupGVWgvoE5vfXWLJLdUN8hBkBe0gBJqqoMNXpXbvVBamCe5qmZIlXOrCiQ/sxepnJRcDFZubGgCU1IRgmVOtFOQyL1wIRRY3F9gQ9NyVqxB7cS21LhyUUMgCLoFfYVuMBxTA/AZYKxqv68f0CnMKo9LAgbkGw2hRg0iM+mgPkOLTPf6fdUtLriSL7lBJvgnE7cB1fPz1FYIhLC5pJbqpuU+qFJtzRmkNcFnZakpoG1QvDyTa2zd9YVukIz3RwR0urKmqAFXbwIfkL31nN+CbFWSr7FZXgl9oRk6U6ClernPxTzUOZ1qTZukJlRn3h4FwIPGlpa3tkrNvpZgoKna3wDFrshjBoyLWZ7PWiUIxqqQwHC3SVBirYrOqG5u9jXVEiUBqfVXroCmkItBd2JFGfVcfF7SkXYo9IL9E/OCm5nkxWxNtzeSzDNZ7ZztisF0NDq4Ghs1zhJ3S6oqsT/pwMCrCx+BguaQ7PIyLz2/PgBeiq1NHG4+mKwxUOsj+s2DcASVtlbXNKxwovsFGyQvxkQJIw707LqAiw9eTtCE9U8/UzrB4sA8s8UHIWEFqGvU+8pYZ5vLt3Xh7fXVsr5hWdfDhsWg3kjjOXxb7oUWQcopSIuabke3X+ALhhp9eNFL2eoCUIYAppEDfqHOF6gT6pb75CAifrjAjC37WhtkodHX6G1sJknzSqHO6w8EfUIjaQkEGwMrMLBj2WwYaaxuaBIwyAtzysqkgtw8YY7HPatMys91Fsa/5udOF8qWLCmd5ZacuQUUXrIEuAtznU4NWcxTdA2I/1kF9Xsy/Esh/yWRb/SvwL6nxHPgdyu7ngSryCS264B4KuNOZVfTWGrjuBP/S4Xx2SL0pPSvwyovWzkEV5pNqeo6N0k4w67nwb9H/+2xVFzdr0ilWGhUwyCU4b44fzIZ89X5zLt/ui0FV7ydjL+672dJuPJ9nNHheycn4Qr494yWJz9iQ33/zMrrk+i8IFW/38HmESls/at+VnF4KYev5fAyDl/H4cUc3sPh5RyuztcQv4KXp7Yfv5Jfb3C4iy+fw6/hy/H14/zMJ3MZxdO4ORWZj3F4EofncLiVw/M4PJlfZ3I4b+cSDk/j18kcbuPnfxw+iMOXcPhg3j4cPoTD6zk8ncObOXwoh7dyeAbvDxxu5/AHONzB4Ws4fBiHP87h/Dx/LYdfwOFPcfgs3t84/EIO38DhF3F4F4dfzOGvcXgmh+/g8FEcvofDr+L9kMNHc7jC4WN4/+fwsRzex+GX8P5c3Y+P42Abh/PrWQeHj+f9n8Mn8P7P4Zfy/s/h2bz/c/hE3v85/DLe/zn8at7/OTyH938On8z7P4dfzvs/h0/h/Z/Df8T7P4dP5f2fw3N5/+fwabz/c/hs3v85PI/3fw538v7P4fm8/3N4Ae//HF7I+z+HT+f9n8Nn8P7P4TN5/+fwIr692o7YxEjKUDFLEDu65BTlJgJutW2h12PTk+BSbGIy/LWPK4FvSNfjpWhPDD4TT88BGkNvdAehv0IaQ260i9CHkcZQG11H6ANIY4iNriX0h0hjaI2uIfROpHFYi64i9BtIo9jRZkK/gjSG1ugyQr+ENIbUaCWhn0MaQ2m0hNDPII0hNJpH6N8gjaEzmkXoJ5DGkBl1EPoRpDFURgVCP4g0hsjosbNI/wRpB9Gf0HcgPYzoT+gWpIcT/Ql9K9IXEP0JXYP0CKI/oW9E+kKiP6EXIH0R0Z/Q1yJ9MdGf0LOQziT6E/oKpEcS/Qmdj/Qooj+hL0d6NNGf0BOQHkP0J/QopMcS/Qk9HOlLiP6EHoz0OKL/GaSTkM4i+hP69GygxxP9Cf0V0hOI/oQ+jPSlRH9CH0A6m+hP6A+Rnkj0J/ROpC8j+hP6DaQnEf0J/QrSOUR/Qr+E9GSiP6GfQ/pyoj+hn0F6CtGf0L9B+kdEf0I/gfRUoj+hH0E6l+hP6AeRnkb0/560P9J5RH9C34G0k+hP6Bak84n+hL4V6QKiP6FrkC4k+hP6RqSnE/0JvQDpGUR/Ql+L9EyiP9CVm5JhJqScgK+bcI9pI5Iv9UDvVkpB3CVbnF+4w+/cIoYPiG0Hj1UudHd3dVWUCGL35kqSdK8bUyIohyD7N/ZxMIHbcBSyLhKnKpCIbX0ZYviz25OWbtlAYgMEhG+WbsJLsR77OLIFtUHh+Df3WYFfDL8ibj58jWjZIb7TF4LML9HMOyGzGN5G8x9g+Vdd9QzEDyE0bBHkVO4BBZduS/kZQJavt2B8Eduuai0FBvmSuAgjFm06thRqC38W27E0eidksY8TokGabkh744krt9Tl2se103FGwa7v7LpxSx3Rb1Hp9aWLSxeVLqwS7zvyAFzbhF1nI04nFQGsIIa3uJwnxY698kSxc2F288ZjaKbwfuV5vNhdZsPIBimZC7nDH3PZN3+H2V8VO76Qr8C8rRuD8zDvUeV2ktdF8ojd5dki+RL2Zy8B1IaxEUAyivSO6r8OX8iu5jpLGK46v/CE5exlFR0n5WR3bLYNqSKu9rLvmPAHUfipYufqbDTwRpT3pcGkvv3KPd8ZKfGRJ1ybXe+J3E1kynE9OJMrt/d0LOYOv8ohH5wmejr3oqb5pfb129r6FoWs7li32Plo9gOkqqOe8FllFanNxWpj6od7xYg/u0jE2iIFys2keJeAQg8WY3Nt9vbrIPi7WTY3y+YBwUR3290wOW1/BoLftvLsSksEzNLeJUZuzs4JXYp5Q2PFiFXsbFVexGWDWPy2veOZC6jmv/sWZAF5s8VYhS10iRiBKjWMvxhO5FbuBMZVd2VXQkXdUJEYuSt7ycZMaEjnzhexpZQnUP22vpi9PTtT4z6bIafzdfRQaEShDwvuLmHKlzDlN4thT3aWyxnrHUr90X1fN3G7DTH6udfdmZwmXhWzYqkwKpbaPafQYKIYWQQS/zUbVy/KY0SbLnt7p6AR4epviROAMUs3krsCU0B3sfMFkgtbZwcMlIryraEro6pZnvBJ5XFoN/SzAndsni001R1J1ZpqgwUb5JRS2QfloGx1/f0N21VZDiYC6TqykqgBs8RImifSrEChL5PK7PO+bGvtE1qHiOHvlEHoJhGru9OTG3twjI1TJ9Cn9ihVHfvGd4lHQ0uhh+9BdZ7uS3Qzd/hLrpxJfapZSPVyzsZbSM/cjybpwTLe60s0iRje545cLUauVzwRn1DR6c9W3FcuzFZCoz3hQ4r3W6Ljo1t6M+o4/WmvyCReNnwDmsxd/GqoGD1r/Clq1nHErCN1Zg1djSY9czIWa99rb/8MYnf0E1SkbWtfPPI1EC85VmrfnJwdbs9uh24doUnvDWJbV9+LlPF1uf5FwmjfbAuvpmw06V2sYasxY6ssjSRnd4qx0nB6Nij58FXA5kGTv5C9Cq4rK0CVaA6AEVvndbGwo+N1yhNnWIQMU7QMr5/hGAqR4S+AcM206iRpJucXGAxysG0UaJuNS2lbKc5Thm3EFXDNST4GkhKO8SUcPWkY/lQXFdtaFej26xCNFGaLkXmKc6dyKy0UQ6NNbPsO+v0IC3NrT+Qat2W/yit2v4LmVL79Rh8xf38CkW3OL6D57e3FpPt8IXa6LKUvkzBRvMXePhTQDUSwyXtEy6soex/IDmMRuM7iE0QGT+dtmWLbGYu9A2fjpQ+mlT7gEqKvssHEhoYD8T4g3bAcVIqV2KD7RF8jgC4w3j2UBsbIN9j7boboahRywY729naMeBiaO+7Ab5EroRpYGTxLDLNfcUMJ0WWnNU35Z8BQnC55nmksfLU330MGCjF8WBkBjbuhhxmjYwLMtyvCue7u2Uyk2UykExUdBz1geps80R3zZEMkd4OnajWLpSPn58qzX4NIOXGRJnzDwjPEBhw88+Tx9uu77MP6JeouyWQSZnHRusS519P5u2zcpYH5hTsyE9sa+qoY/lB56BsSoLArFy9R7D+534rZouLkD0AACKXIc/iExjK/+FqNRXKBCL0XyxXDVrGbfqWm0rroBgR77WS8ULM491ag4XAk1SgvQ8j1QEwuqYjcbau48m6HPLYCW8sdHufc627rtlWE77ZFBwMXG38ijWCsPnGygrM3d3jri1izx17+iduy1f5Il/giG5jGieE3PMUH7I9stm322F0HoCE20GAaH7vGuYu32n/6cyj72s4ff0Z2R/ZhX4AqUBps6clfiuHjYtsnfaJls5wihkeCcYvP2Nt/RlaZ2/rEzV9axdg22U7ZLKQNDstj0JPsYqQCTGWDGE+Hms5FNrFTBBcvz84R284mtZTXrcGwNlSMJIlhi9idRNlmAct2KN0mO8TIHUCshDJm2ehyt8uGV9zF3Vhj+JXQRnfnnD4s0oHWzey9hRbfWW+LPkMz9MfPkWbxMy0e9u69Oh7ySr+KxXqn1ZFPfLzwREICDgqTyKAwXj8orMFBQTlGBji2Pn8VhD0a6hYjHhBxiic7k5gzQoT0WxxgaShUzrZhs4PNY8rTmB2v4zzLHW60XduZ3APfHapbgy+SOVlF+JQ8jsyjRurCRageO/oyLKjtDATxpRasIs/e8QXMXaJdf4dd7A8v5oeDicehnHJEzrucGn7c2QciknU/hApPGOLEpmUQ+5XFCHu/p9OVPOz9NiUJmiNahePs/iECaYNLSRuMTZjvfGSj851lR3EAjyHffMKXpuU7QPhiStFRTeB5Gkiypuj6oYgDYwSZ1mNrlYiRHE+k1YZa5JE+cjt2bWiy5sGk86rzLZjIRjLVGT7OTCYfI+OPWPxLwmpvx2eF3JHFNveVix3yJbgQs3rCl4ttr9jc4cW26C6BK68CZjzhHZ7JfT8cDrZ7ig+p4eAQhIP/JuHgcl04OCBw4WD7MRL8oBKUxzP5tDu82735LKwad4htPRAU9qBoOdgYQ4g2Z5U7wXrzOuWv+/35gy+oPxeJ4UxPuBmU2AYe/ak7PNuBQ0OeaiPWVewde85CI+Ooi/NnBzj8RrS+4kRhVCQEbvIS7hoop7/E4olVoWOEpmHERRYxUqIAezJ+j7yQnAdJ23aLchvI1ztReQGS6IgYHRHnfNlfsggT6/Aryu8A2taefS/INSl+CbwWAXw2S1B+AhybiGCvfUmnvXA5cxCV2gapkgd1PG9B2DaILlaawBTOvRvx5sxL+AQLYih/dOhZ9IFulJ3w8n7avtqh7a/29hpATPpatAK5O+/KLlHWjUMr+GFiMdBCanAqlS3/CIb+VE8EplbNEHPSLxM3LV5EP2L4NfHUUWz1zQrZKOhMLoHxRZz8CsH6rgFvsAJu71hKRtS3xM1nAPvsrGh5SwwrmrzuyVvtq3FDUSzeZl8tEX5YGG7KinfAnCPqkGtvdw2lk6WseEfLEztLLCTgezoLX6XTjFPKC72kE3nCU7aV2XAkzhTYiIyNxRX+Zq+6RrG3K+lYOCxHoQRP+GslQAqBPh0StrmwFBcrxeWwsElbJlfUKsLe7XLuJFEGPWkqgdJKt82xwSxojoPOhuaQYirCp92RK+w5KbiBUmof5sI/qWL3HDJ5wK6Q5W6LQQN4IFKvxgfNKjpLwV3Elz97+DfDnVJzGOYzYmcwyR3x7LOJ9j9tJ83yhWh5Q7Xu5tNjRcsrYsMruKsiTt6MDNg6Ewltec0dLt/nIFsuzp3iqbM4Wtv/lP7+D5azkabbxc3fXiPe94lKheX9Drf9T/LHMEYfIyV8ZVLCNmTgJDkGknzsEGNb3MV77B2TYhiod8pT3LFrHaGJnvCbOGMdXrrqDpsQGuIJv6d0HEa7HvaE31cejOLXD5wnPeHXPJN77KufxmXcSTDdWZzkO0RYgXss2z3hAyDENeL40x7LAVQURR//Lcxj3JH07SB1+u5+w56DId8WN8dA98+p/G9DAXedAI/oI/lOm+SDScpZcfNZyHeI5ju7CW/A4mBchD0zU/mlgtErZXpBFg1Ykcd3eJcJxPUXwTC36s4iGBDeBg0fLCuL9qArYwHOk4qXZvw+PzHjBYNpRnkmZOqdq+Zw0hxvGOSoZFXJRZjDg55cRritwJm3kQ1WsR32jcdIacqJw9iLupU/QmNEn2S7VY4Bs7zCstwBWXpXIH/P5wPxP8L4r43iaqbCQfeNxpCNKPCOIavuBudIUW7DSiF8BT8nix5HaDRb8AxZdSdhuFahQX7B53Q5PxpmDZmhC3GrgCyLrvgcZx+nlHwsAOKmqOyB7iretxV3G28qvbl0aektpdLSLdoI7LaYR+BCiz5e/3gA7kkJ3NMG4B6VwD1hAO6hCdwXDsAtJHDbBuD+WtBzfyeYcx/CTVN1D2DKgynJeVnCA+VTMqOvHtdsOow8zs0ONx0C70rTMtiOcAy/QoaTvRqGZ/kS7kaGX2tL+OQEx3AzMrx9QsOg8AxXIsNuLcNbfRzDKGT47z4NwxW9HMO3n+HmSy/15j+MJMtiMteFsSPamozTyO5oM6RR2UKI3hxEvqUEGWrAwaMVGnq/MuEQ8Wd7+w68ADNhe8c2MnHUzobbn05o1XsHaNVbaS0QJ2blQpwIq3OpoXNzWdgIryZTKlwA42zHAX0Vpy3LEqYtWxIc5OcDOEi7QCcrdLaPImBgugGnB2QrY741cVOkPd+a4LHWATw2SWvBnoPQMI8I1OZX9y8Bh8ab7uqDuJKjijZjpTC1q8Sp3Wef0Rkj3rhUNhw0jiw9B2hk2XOARpYS5ZKLQAwfiGhU2TufUvankb0NZgMQ+X9nje8NiWCE/xUnIxpjy9ec9zq3v94bPsUwDPVFnVA8ndKe+BQH2a2o+xqB7XKQOXazAsvvEag64srQA9QOSGz8Nc7J8U6p8tgn/bCIg53yzUHNrorrAJmuVcAsrAN/moIehMwu5xdRX6oqReBTOhHstnZVltB5daq6Grj0IK2CIN9VQM14T1Q5coD2PEcqnYjjA1bK7z/VVP7aJ2Sah52no4hVjnyw6IsujFf+1QF95c1pauVPfkorJ8hoVPtiIi+rvDWNVo63vZXLtZXP5SqfxCpHPqy8LJV1PmoMra8/mK739XcH8PWNJk7m/4SOhuU9qk8+iHdcYIEgkQXCDfoFwj/kWmd76OC8ez91aZsg34r+a0N3Dkn06z/RlR/qoa5sU2r300VnFi7jq7E6aMvQEl0E+YcqG99DTfntx+rE4dcOuqHwF9LG/YHmduCMjiEXoS9wQV1Zilees2sivSICSAgPEFcixy8GayPXZQiOJatXPwmW8SvpeOXfztLB5poL6OBSBYHPPkTJAkGjn8JQRqI8MlxygRrtF+bQaG8jLjl0aU5/tCcQBALsUmq0X5Kqd88RSXr3PDzAMPNefJjZO4lWjF0JKj44qb9iAkHF2J3UirvS9BV/nDC+vTBAxb+Ga8rF+8AG//sbDLdfoxQwu0ycWA7/mPruqH1sOw6cyBEqpl8jRcjqIMSqVsJ/YB/1vRxF+QhmuA7l2Y9wbtxfC45nu86QWWqmveONM+rWvL19PXxXnkP2P5zRzCMes9FdB+Jvz6LU7bZ+T8DBYszHOPYctLf/x/fgc7jFbu94BL/qt9nbR9r0djqaZm6nD9OM48eP9tEbXntPUescQaG2n+Kk5phjH9HhEz1HHT4x2itPfkzj5zIkVmIR/2kzru+vrAj0AbWIdRhWvayI15CYgUXgQ0Vq6CS3qLnBS3+zhGzRa+1zSYIffTPAdGW/0D9uuMOp5HZAqlqX9i6IQV3jE+o6NUBdB4T+YYLVhV/Psa6yhLpGDtA/ki3G7VC4F3yqOzlbHQvXCupY+MRH6G1LyUKyw2Ohoq4V+jfg8HvkhWTcdcYNuMNQUvQa2v+jv042ru7VD8ladeOlmqjUfen5RqXfJyh/9wDK15soP5NKk3epJlQVX3q+oerihBj5xQDS7LHQZfXTH1BPJzalu5OpH9KJxlMCnWg8jg2x+UPNROPAnvguWsfPrbRZHid3vKPrrWr0XTqBqkTba2jdhH6VCAQqYR2qSscSZiUbElR6KMlcJfzVppGBd+8xCRR3f8gFisoPNPv0lj30uZYunL1UkJ16V/yBgk14u0jJwOwYCshtpwoHTgbSPeG8+FM5AOL9Kbar72L3EUH/MhtZW71sVddWz1sN1laPJaw//APMya43mZPted8kxt37ARfjFuzRaG99/we1d3zwD2p/OknV/liSgfbvJrT90wO0/aNwrZe6HR1oU5RN77GJDo4kC95n69m18VofM6p1fUKtqweo9XYTj6vdTW2O3q3aHLfXlCF7qM37kPh4N47enysnd+NOPq5W2mMYbWGmbO84QZ470G2nt7+fsOr94wCh/XGhv2Oyu8qPCwPcVdbW9VZCdPvtAPHkIZPodsN7VEnnLgjMi78xHsoLCdNRJX0Xjv94Y+dz5RhikdrsejIBuZV0FTIBkUhf0U5A/qGp9vpdVMSH3sVWK8+mzy/3mbTtA7voQnoZ4bZmXVcibOyZD4u0NR76XMlPQfDeYqOsFSzrRJr1GIx2G9dUclk979EbNfD1k110/h9Fu333NcGjX39tbL9v3qUF/20nVL3ZiGPnu2SQeXOMJiLvGnN+EfkfMvP8d006xcldXKd4/V1NILpj5w8Gop/uMghEYhjv18nJYqzMLBC5w7g+xHnzx4K6D7TL4OGY9r8kdLpO807Xe6cmCF3xDheE3kJlsMLU79VnaL6nj7tpK/xtQhBaOUAQqjVx1P3vUA/6yw46udK6Gzr8vp10jZfDr/FydtJHgJah/ZaTBwCq/5kLW5GJlbWD9rZl9Mb1zdlL/i9V+P4OWuGf3qYVLlErxOeZ8M7lXHLnkj3HFGXi3ce4ydO39NnS0K3qSo3tLuT8M3cX8naoK7zUt+l+RpEgi/TWNtZ4Ff2qq3GOpsbxZjXacePgnneMo8f6t2nNRcrq7RhHYsrCd0i8gclc3bfGeX7yNjXTjZAjOvNbfNq6XBBKF1eJbUcy3eGz7sgtWWjeKcS8ExOfxGV3dUZtR+ecTR94iNySOVCen7E8h94ieTJZHsdAedpZnudoHvqQX+QSzDKBZBkTb/mjTKWfEtZU+nzN1sybSm/R3J2RF/Ub2ZOdHIF/vW4Nw3U8QzowpPe6NAzzeIYRwDCidxa3Lj+IGyydhdnKWDTu7rOaRft35CI+shIDOaNHtFeHxehVh/IJXk0Ckn++qP9590poo4rI1RW4QfAUmXTMz7R3/IpYZ5w7ErCJxb3yitK/oiF7izTSX5CoP+fQk4jkXqi9d8waT2QKTGvkCTilCY1RpzOe4s9Df8ThfuzfyDhILb0FqtwXeguqx8axYUuceZO644k3+RaxcbfNdM9PVYnh7+JbqnfalHT6CMZN0X9/i/weQH/9yFna5PJbjC/yJhrMtLy/Mv5ylf+mgflXM/4RKv8U5I+zr6lUnoArSuhvav+5vjQcK13sDp8sXeQOv1e60NM5sdmRJSwSO6e2QlrlmfyZc6+4+YwVf5mlLH2DPsZ+Sfz5MbyJfbIcyoiN+AhMaoFWDB0mNluqGm0LJ+/XW9hvvNhPuiyaX8Nq35tG3lNV61sxLSjXNjQJ7mnzswLNvpZq/Kl6FvxPfiFem1XX4PcJLVOE2ZBmjUeWpqy6QEsWvhSkoWm5wL934Ior8DUAgSagQl45qynk92c1BeSsFdX+hloha7COORiqga9CQxO5nuVvkKF6PyndH2hanjM56/YGuT4Lf1Wf5cy7YpJQFgj5a5smyUwKlEj7WpR5znxpjmf+rFKPJM2TnEXNK+X6QFODdzr+1j/ozFtc7Q/5XPgmCNe58BdUydVNtfg6BpZlYP5il/pTf9e5yVMwC1TjMznY76Er55dofmcd/12o+r4adn3V/BLD68fmUXytyfUudr1Ld31geWe653O2Owf9ZriaVjS0BJoafU2yLqdWnrxKY3nU6wK73lxZYvh+NtUOOBEiP6phqf59QPHfd1Zq+Xt+gL9HV76jQstvGW298i72m+vXtsVi+Ez2EuzM0P1WQoqrtHoIFbhEa4U0C9IHIF0C6Z6+WGwN4qdjsXWQLoEZpII0pNh9n4I0E9I9kOZBmglzzWWQPgDpU6x7j1D79R0LBEurwzI6Pc22xpLmGMF+t/zB67EY/3tbY376G2Hk73sVZMI4nuGYnZF5rX3I7bZVwjWjrry8IHsCn9+qy6/Wh7qn6urDH8FVAk5+916a4eDf52i9o9JDSkqz4quOrGp5hex3yzmQb+5UQUj+vqoE887KyJyVkTUrI2dWRl5pRtGcjK4L29JWp3amPJT8sPX+JFLu7/B3y6disUcx2M3KcJRmZJZn5LVZcccJy92K/ga2f4fJoyuzNKNEU2Rcj++xLWGCNJbla0uiOP5uoBnwiTr8R9jWBng54GsN8JsBt70Wi43n7ITvXsD7FOuA3ydQfR5OcmVkPmR1ZWR1JrsyclaniBl596eKGUVtaRUZJX7UAPTIITqBZqCfjcqPPgflJOl8PGZ9INUaS5nCftr/ItpwOSO2k7ul7Mf0VmRZaqG/9FfwyvQk+pqAP+A6Dzd/cCpXiX9GW+kLCo7jT1wfttK3JJxEYpOVsp1FIjWZvgcgA2+MPpNCicFo4SOMGIfEtFT62oRiICw3pdJ3GdyIxFOplG0E/nT1ZSAeVIe4OTbaLf8G9VjqGbELK20aRF/y8AW5GzuEanoQr8SG0KIvwB8O408pUGofStsBRKtqsTNDaZ4jmMeeQX9CLmNp12fQosmVhgz6Y25y5VcZ3BsPns+g1ilF5V7JoL7eiwLuGE6d4Rb8ae6wC+jbHxYhWxkjtuKV0AX0d+7kylOMIFf2MIIUkApFrVHfZ/HYSPob8uPYln8byb14Y8goqs8N2IxjR9Gf3Ndg0e5RHNsDjO1RZHuCse1Ftm1AdKh+NXcstQGRbeEllCDivMQIIugm+POemufR8bTovej878CfW6AZb8CfExdl06bfjt1lxkRK7ECiBP6kqS/3mAMyVaieiAJOUf1g02SaZxHGweOX03rGTGX+LCbpZkb/+vzr86/Pvz7/+vzr8///p3kMW6+w97hXjikZcF9ATXenaOkeHX2G0eq7qXoupuWq76TaytZJI9X3L7H3iKvvWFLfOaW+o0lh19V1gfpOrRNnYwHy/p2kkvh7wcj7dQaVxN+LRhcSlFbfrbWZXVDfqaW+I+pCnX2s/S/iYu+jY+89StGul9R3f6nvoFo7vESDPz6sRCO3jRlqkK7+szGqT5+D8scYrcpxjNG3Okr+n/pJ/D32us9FmVSOy1g6g6WzWbqYpXUsXcHS+1n6GEufZOl6lm5j6W6WHmLpSZamsvX1RSy9jKUzWDqbpYtZWsfSFSy9n6WPsfRJlq5n6TaW7mbpIZaeZGkqe+/uRSy9jKUzWDqbpYtZWsfSFSy9n6WPsfRJlq5n6TaW7mbpIZaeZGkq668XsfQyls5g6WyWLmZpHUtXsPT+0cb+M6es7IqsnEU1oSY5lFWYW5RbODU/RCjnPc7C3LzC3MLJFBcYk9df3bQ8a4WvJYjbgwW503PzphbSLPn3yC2hoLwyPytHrl4enLbA5XGVVrmkgul50+rwNZqTs3JwD68WdxU9nsUVNDvMx3ODKxvl6hpI5Raa1qvfGppkX0uzkNsUkH25pbPcU6FoRi1vCuXWhBr8tVMbagVC1VcH64Xc2pVNUB5N5RZ6hQmsISS41uLzVyMj+9bsl7HKBvgr+1rhL8jdANcCtdVytZDrq5fqWqobfVJ9bUs/BYV6vewVppJMXpdMypCqW1qqV9Iy1O+3eluIYNWNDV7IF5DJH1ovraMmGBRyvYFG3Cv7h/vxaBaj1TjWf56GoImvgsmq51JB+y7F/vMq2PvmdPzJOtqpyy+z/DIDsn8gP+53nIQYqOZX4/7jDKhleIpunIjvS7KYn6QbF9QA+xQbF1KZ7jZdfF7MWJN048xTg7Tjipn9bmExXc2vxvFb2YD3kE5+3bEhwm1sjFBpdZzoY/nXCv3yWw30v4PZNEk3Lj0+TDsu6e2n6t+uy6+Oc2uHa8fFFDb26/M/JPSfscLPC3ou1o73Zu0f1uUX2HigVrDGqttH1qWP6vKr8541bOKRn2+cX/08ocuvzmO2VmjHczP51+r63w6WfwfLX28duP6n9P03fu4Lpe/6gfrX6/JvYPk3sPzlus0/vf906fLjtitN2XzPOnD9O9leuFU371PPldHrq68fH+Cwc/nVeaGy1JhfTx9m8sfnUyz/sXPMf5TrW/y8SD33RzVMqi6/qlefrn71/b190sD1q+kZXX51XiqwZI9l4PypFm3+Pex9kHuqz83+6RaKxetn7wFWWH6brv3148EwVn+eDlfz328y/qjpMEH7vl7101TD4odl4PjL+y7/EW9j/ZG9HBc3IEWD+DXIpP7MO2g6zTFw/QN9rMCtjsdaPCk+zmpxa3z81OLJ8XFRi6f0j3caPDU+jmnxNMN1hhWs0meID4qPJ1p8cHyc0OJD4vFfi6f3x3UNPjQer7V4RjwOa3F7PL5qcUc8bmrxYfF4qMWHx+OcFr8gHr+0+Ih4XNLiF8bjjRa/yHB9ZYXVpBoftHhmf7/X4CPj/VmL95+LosVHJ2AWErOPx/Q4fcduoh2uJv2pv13Gc/MkC9SbojsvpYPxq/dJJ3LjEuLq/dmJXLwm5TNcfacy/sqClHMtxR9lFYgM79GVE2L4urkUf4fhrzO8i+17zGUvDVYsVP5knfynCG6P3/dV4wKen4P4Kh1+I8O7dHgnw9X71iq+heFrdPhRhq/VlTPWyspn9+3VdyFXMFx9XkB9t/EqhqvPAaj48wxX77er06Aow9X77Oq7nC9Mprj6vIF6D7mM4Y7rtPxBhq/TlfMkw3t0OJ47ZOSH+wh/Yj86nMzaXRcfYgx36Pa1hqdQXL/flZNC292ia/eZBE/s17ewcpp15dxK+BPjg5leYcI/TOjT9a+fpRjrK5j0098S/sT48CKZl1+QIP8bDNfLuY+UkxiXDqXgmJ4YZ46bnO/kMDkP6scEh37H4oA6JnsY/qyuHatSjc93esSk/L+Y4PtTjc8H+9IET0ozLuciE7zABK8leOI4dasJ/8Mm+G9N8PUm+HsmuMVmjE8wwX9sgvtM8DWAT0gaKpQwfdV91t/bjM/LOmxSzhmb8TlaEwYZt9fVg3CO2D/uq+uPikHG5ftN8HtM8P80wTeZyPMBvtrAoL8cMiln+GDj88pmDjY5r2+w8Xli9w+m/WjtGO0++G8HG5+3tg3LSRopKDo5d5rU+9Vg4/PKBg0xOb9xCC2/R1d+gQn/nCFU/krWjj6GX2/C/4IJ/voQ43PkPjfhH5SOPKMS7HBhujF/XrrxeXQ+E/4OE/wZE/xNE/xIurG/WYYan2s3aahxOVea4O0m+GMm+H8NpXaz+bR2e96Ev88ET88wPu9udoZJ/80wPq/vFyb8L2bQ/qhv364M4/P0PjEpZ6bdGL/WBK8zwe8xwX9pNz5vcL0J/9sm+FcmeIrDGM920H63boz2ftlkghus16a1BALytOaV1bI3UOtrmdbcEqjx+xqD06prvM7C6dPKp+FxUbne5mZyWhS/KZ4vxB8RDYZqJLcU55RuNHt+1OmUJNzilxuaJMlTOC/QRM9hO+fHe8vz6EFb5/P87d+VJ/8c8hTik8rnxKk+YftDooTkBj/oG6yvbvHVSi2+OneVPGOFzysHWtzzqvIkWho5h66q2l01XXK5XKoAc52FkoQltVQ3kbaYjn/yvX527qGnSJIaAuRmCJ6hdz6PVJ8Dv/6R53PJonsK+xyyGDx4/MO5+h9v/mHeYq0KVedpparzt1LV+Vup6u+yUtV5WKnqvKy0+DyttPj8rbT4XIX3tshBOVRXl+sVJOnasgWSx121UJKE/hNSJblR8uJJqEHBAJKk2oC03B+oqfZLtdDtglJ1qFXwBhqb/T7ZV5s7o7go35hJ6r8vKIHhW1YK9N5ibaixcSVk4Sip/3YiY5Wk2QtKK1ySa145nvNKJGffmdbzZ8+uci2UFpbO8riQQ1NErRYgB/0JUvkN80or3GUC3ohUMf3hkyUl/PF9Ax/WqeOlhwp6gyGiuRCv4TzPrdRLYHika4KYhofOarhyi8/p+FxyRGNi8dxBkAYmGuBcW60MTqfArGN8mKS2bHpsI8PYKYzkLEgtlHCco+7ygKd36rVJOAdT38r9Z00mVmNy5mxik5qeD5tQGz6PAG3u90vx03T/vtNztSWTAzQNFEg8XVcn0YDHK8+XyI+spFDQV5t4qq5OghafL0GAgc6+1WanZ3/qChjgfGd9pzc9wtnIvRMONzUME0YnNBv0JIPzVxOL009eCirml7Opi8F5v3qvAd3VcJlw2nGiM5JDchNh7vhmffm1wYBUD8MwWJaeymrYITEUsvnVP/GYaX1QY4e66l1Je0yyXrvEA4b1KtYEg5y7xM/Y1hd0bgfvlpRwh8cmHhdsGGISzg5OLER7vrJRKdrDy7UlGB55bnJSuC4ukzN2DaLH33diti4u+AJ1eneKnyuu1YAM9H/fqdW6OsmPQBNc6JwPjTYYsw1OcjeLBSYHchu1J3eit84U5Okqo6O4E93mn3DktMGoaaBd/Lx33TXNOc9wjZ27rD/GPdGq6oncBtMfeqa2gRD6A8cTXbl5ZX/LOwsTz63WT0oamgQa1/4HvgJuIEeKAAA='
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
MOD = 1000000007


def init(fac, inv, finv):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, fac.shape[0]):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def com(n, k, fac, finv):
    if n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main2():
    stdin = open('/dev/stdin')
    X, Y = map(int, stdin.readline().split())
    a = X + Y
    if a % 3:
        print(0)
    else:
        d = a // 3
        if X < d or Y < d:
            print(0)
        else:
            fac = np.empty(d + 1, i8)
            inv = np.empty(d + 1, i8)
            finv = np.empty(d + 1, i8)
            init(fac, inv, finv)
            ans = com(d, X - d, fac, finv)
            print(ans)
'''

Submission status: Accepted

Solution code:
def mod_comb(n, r, m):
  nn = n+1
  r = min(r, n-r)
  numer = 1
  denom = 1
  for i in range(1, r+1):
    numer = (numer * (nn - i)) % m
    denom = (denom * i) % m
  output = numer * pow(denom, m-2, m) % m
  return output

x, y = map(int, input().split())
if not (x <= 2*y and y <= 2*x):
  result = 0
else:
  c_up = (2*y-x)/3
  c_do = (2*x-y)/3
  if c_up.is_integer() and c_do.is_integer():
    c_up = int(c_up)
    c_do = int(c_do)
    result = mod_comb((c_up+c_do), c_up, 7+10**9)
  else:
    result = 0
print(result)

Submission status: Accepted

Solution code:
MOD = 10**9+7         # 問題に合わせて適宜書き換え
list_size = 10**6+100  # 問題に合わせて適宜書き換え

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = ((f_list[i] * (i+2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(-2, -list_size-1, -1):
	f_r_list[i] = ((f_r_list[i+1] * (list_size + 2 + i)) % MOD)

def comb(n,r):
    if r == 0 or n == r:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD

X,Y = map(int,input().split())
if (X+Y) % 3 != 0:
    print(0)
    exit()
N = (X+Y)//3
X -= N
Y -= N
if X < 0 or Y < 0:
    print(0)
    exit()
print(comb(N,X))

Submission status: Accepted

Solution code:
X, Y = [int(_) for _ in input().split()]
mod = 10**9 + 7

#a(1, 2) + b(2, 1) = (X, Y)
a = (2 * Y - X) // 3
b = (2 * X - Y) // 3

if (2 * Y - X) % 3 == (2 * X - Y) % 3 == 0 and a * b >= 0:
    f = [1] * (a + b + 1)
    for i in range(1, a + b + 1):
        f[i] = i * f[i - 1] % mod
    fi = [1] * (a + b + 1)
    fi[-1] = pow(f[-1], mod - 2, mod)
    for i in range(a + b - 1, 1, -1):
        fi[i] = (i + 1) * fi[i + 1] % mod

    def comb(x, y):
        return (f[x] * fi[y] * fi[x - y]) % mod

    print(comb(a + b, b))
    exit()
print(0)

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

# A=(+1,+2)をM回、B=(+2,+1)をN回
# X=M+2N, Y=2M+N => (X+Y)/3 = M+N
ans = 0
if (X+Y)%3==0:
    Z = int((X+Y)/3)
    for m in range(Z+1):
        n = Z-m
        if X==m+2*n:
            # これが遅い
            # ans = math.factorial(n+m) // (math.factorial(n)*math.factorial(m)) % (10**9+7)

            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 )

            ans = cmb(n+m,min(n,m),mod)
            break
    print(int(ans))
else:
    print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
def power(x, y):
    if   y == 0     : 
        return 1
    elif y == 1     : 
        return x % mod
    elif y % 2 == 0 : 
        return power(x, y//2)**2 % mod
    else            : 
        return power(x, y//2)**2 * x % mod
X,Y = (int(i) for i in input().split())

Z = X + Y
A = max(X,Y)
B = min(X,Y)
C = A - B

if Z % 3 != 0:
    print(0)
elif A > 2*B :
    print(0)
else:
    N = Z // 3
    if (N - C) % 2 != 0:
        print(0)
    else:
        M = (N - C) // 2


        a = 1
        b = 1
        for i in range(M):
            a = (a * (i + 1)) % mod
            b = (b * (N-i)) % mod
        c = power(a, mod-2)
        ans = b * c % mod

        print(ans)

Submission status: Accepted

Solution code:
import sys
x, y = map(int, input().split(' '))
ans = 0

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

if (x+y) % 3 != 0:
  print(0)
  sys.exit()

m = (2*x - y) / 3
n = x -2*m

# print(m, n)
if m < 0 or n < 0:
  print(0)
  sys.exit()

ans = cmb(int(m+n), int(n))
print(ans % (10**9 + 7))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def modPow(a, x, p):
	res = 1
	while x > 0:
		if x % 2 != 0:
			res = res * a % p
		a = a * a % p
		x = x // 2
	return res
 
def modInverse(a, p):
	return modPow(a, p - 2, p)
 
def modBinomial(n, k, p):
	numerator = 1
	for i in range(k):
		numerator = (numerator * (n - i)) % p
	denominator = 1
	for i in range(1, k + 1):
		denominator = (denominator * i) % p
	return (numerator * modInverse(denominator, p)) % p


if __name__ == "__main__":
	X, Y = map(int, input().split())
	if (X + Y) % 3 != 0 or Y > 2 * X or Y < X / 2.:
		print("0")
	else:
		n = (X + Y) // 3
		k = Y - n
		print(modBinomial(n, k, MOD))

Submission status: Accepted

Solution code:
import random
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 * 2 + 2)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
x, y = map(int, input().split())
t = min(x, y) // 3
if (2 * x - y) % 3 or (2 * y - x) % 3 or 2 * x < y or 2 * y < x:
    print(0)
    exit(0)
a, b = (2 * x - y) // 3, (2 * y - x) // 3
k = min(a, b)
n = a + b
print((fac[n] * pow(fac[n - k], MOD - 2, MOD)
       * pow(fac[k], MOD - 2, MOD)) % MOD)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd


def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a
 
def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
 
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def main():
    x, y = MAP()
    if (x + y) % 3 != 0:
        print(0)
        sys.exit()
    m = x - (x + y) // 3
    n = y - (x + y) // 3
    if n < 0 or m < 0:
        print(0)
        sys.exit()
    print(comb(n + m, n, mod))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
X, Y = map(int, input().split())
a = 0
b = 0
for i in range(X + 1):
    N = i
    if (X - N) % 2 != 0 and N != X:
        continue
    M = int((X - N) / 2)
    
    x = N + 2 * M
    y = 2 * N + M
    if X == x and Y == y:
        a = N
        b = M
#print(a)

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

if a != 0 and b != 0:
    #print(a, b)
    ans = cmb(a + b,a) % (10**9+7)
    print(ans)
elif a == 0 and b != 0:
    print("1")
elif a != 0 and b == 0:
    print("1") 
else:
    print("0")

Submission status: Accepted

Solution code:
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 )
x,y=map(int,input().split())
if x>2*y or y>2*x or (2*x-y)%3!=0 or (2*y-x)%3!=0:
    print(0)
    exit()
print(cmb((x+y)//3,(2*x-y)//3,mod))

Submission status: Accepted

Solution code:
import numpy as np
def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**6
MOD = 10**9 + 7
fact, invfact = make_fact(U,MOD)

X, Y = [int(x) for x in input().split()]
if (X+Y) % 3 != 0:
    print(0)
    exit()
r = (X+Y) // 3
k = X - r
if (k < 0 or Y - r < 0):
    print(0)
else:
    print(fact[r] * invfact[r-k] % MOD * invfact[k] % MOD)

Submission status: Accepted

Solution code:
def cmb(n,r,mod=10**9+7):
    fac=[1,1]
    for i in range(2,n+1):
        fac.append(fac[i-1]*i%mod)
    ret=fac[n]*pow(fac[r]*fac[n-r]%mod,mod-2,mod)%mod
    return ret

mod = 10**9+7
X, Y = map(int, input().split())
Z = (X+Y) // 3

if (X + Y) % 3 != 0 or abs(X-Y) > Z:
    print(0)
else:
    print(cmb(Z, X-Z))

Submission status: Accepted

Solution code:

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


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])
            #print(result)
            result%=(10**9+7)

    return result


X,Y=acinput()

import numpy as np
from numpy.linalg import solve
 

x=solve([[1,2],[2,1]],[X,Y])

#print(x)

if np.all(x%1.0==0) and np.all(x>=0):
    print(cmb(int(np.sum(x)),int(np.min(x))))
    #print(cmb(int(np.sum(x)),int(np.min(x)),10**9+7))

else:
    print(0)

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())
s=int((2*y-x)/3)
t=int((2*x-y)/3)
if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print(0)
elif s<0 or t<0:
    print(0)
else:
    a = cmb(s+t, t)
    print(a%(10**9+7))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
sys.setrecursionlimit(10 ** 7)

def mod_combination(n, k, mod = 10 ** 9 + 7):
    def extended_gcd(a, b):
        if b == 0:
            return (a, 1, 0)
        d, x, y = extended_gcd(b, a % b)
        return (d, y, x - (a // b) * y)
    p, q = 1, 1
    for i in range(n - k + 1, n + 1):
        p = (p * i) % mod
    for i in range(2, k + 1):
        q = (q * i) % mod
    return p * (extended_gcd(q, mod)[1] % mod) % mod

def main():
  x, y = na()
  if (x + y) % 3 != 0 or x * 2 < y or y * 2 < x:
    print(0)
    return
  n = (x + y) // 3
  print(mod_combination(n, y - n))
 

if __name__ == '__main__':
  main()