{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eAlice, Bob and Charlie are playing \u003cem\u003eCard Game for Three\u003c/em\u003e, as below:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eAt first, each of the three players has a deck consisting of some number of cards. Alice\u0027s deck has \u003cvar\u003e\\(N\\)\u003c/var\u003e cards, Bob\u0027s deck has \u003cvar\u003e\\(M\\)\u003c/var\u003e cards, and Charlie\u0027s deck has \u003cvar\u003e\\(K\\)\u003c/var\u003e cards. Each card has a letter \u003ccode\u003ea\u003c/code\u003e, \u003ccode\u003eb\u003c/code\u003e or \u003ccode\u003ec\u003c/code\u003e written on it. The orders of the cards in the decks cannot be rearranged.\u003c/li\u003e\r\n\u003cli\u003eThe players take turns. Alice goes first.\u003c/li\u003e\r\n\u003cli\u003eIf the current player\u0027s deck contains at least one card, discard the top card in the deck. Then, the player whose name begins with the letter on the discarded card, takes the next turn. (For example, if the card says \u003ccode\u003ea\u003c/code\u003e, Alice takes the next turn.)\u003c/li\u003e\r\n\u003cli\u003eIf the current player\u0027s deck is empty, the game ends and the current player wins the game.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eThere are \u003cvar\u003e\\(3^{N+M+K}\\)\u003c/var\u003e possible patters of the three player\u0027s initial decks. Among these patterns, how many will lead to Alice\u0027s victory?\u003c/p\u003e\r\n\u003cp\u003eSince the answer can be large, print the count modulo \u003cvar\u003e\\(1\\,000\\,000\\,007 (\u003d10^9+7)\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq N \\leq 3×10^5\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq M \\leq 3×10^5\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq K \\leq 3×10^5\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Partial Scores","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(500\\)\u003c/var\u003e points will be awarded for passing the test set satisfying the following: \u003cvar\u003e\\(1 \\leq N \\leq 1000\\)\u003c/var\u003e, \u003cvar\u003e\\(1 \\leq M \\leq 1000\\)\u003c/var\u003e, \u003cvar\u003e\\(1 \\leq K \\leq 1000\\)\u003c/var\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eThe input is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e \u003cvar\u003e\\(M\\)\u003c/var\u003e \u003cvar\u003e\\(K\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003ePrint the answer modulo \u003cvar\u003e\\(1\\,000\\,000\\,007 (\u003d10^9+7)\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cul\u003e\r\n\u003cli\u003eIf Alice\u0027s card is \u003ccode\u003ea\u003c/code\u003e, then Alice will win regardless of Bob\u0027s and Charlie\u0027s card. There are \u003cvar\u003e\\(3×3\u003d9\\)\u003c/var\u003e such patterns.\u003c/li\u003e\r\n\u003cli\u003eIf Alice\u0027s card is \u003ccode\u003eb\u003c/code\u003e, Alice will only win when Bob\u0027s card is \u003ccode\u003ea\u003c/code\u003e, or when Bob\u0027s card is \u003ccode\u003ec\u003c/code\u003e and Charlie\u0027s card is \u003ccode\u003ea\u003c/code\u003e. There are \u003cvar\u003e\\(3+1\u003d4\\)\u003c/var\u003e such patterns.\u003c/li\u003e\r\n\u003cli\u003eIf Alice\u0027s card is \u003ccode\u003ec\u003c/code\u003e, Alice will only win when Charlie\u0027s card is \u003ccode\u003ea\u003c/code\u003e, or when Charlie\u0027s card is \u003ccode\u003eb\u003c/code\u003e and Bob\u0027s card is \u003ccode\u003ea\u003c/code\u003e. There are \u003cvar\u003e\\(3+1\u003d4\\)\u003c/var\u003e such patterns.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eThus, there are total of \u003cvar\u003e\\(9+4+4\u003d17\\)\u003c/var\u003e patterns that will lead to Alice\u0027s victory.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 2 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1227\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1000 1000 1000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e261790852\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\u003c/section\u003e\r\n"}}]}