先日,ã‚ãªãŸã®ç«¶æŠ€ãƒ—ãƒã‚°ãƒ©ãƒŸãƒ³ã‚°ä»²é–“ã§ã‚ã‚‹Oã•ã‚“ã¯é‡Žçƒè¦³æˆ¦ã«å‡ºã‹ã‘ãŸï¼Ž 観戦ã—ãŸè©¦åˆã¯ï¼Œãƒãƒ¼ãƒ Xã¨ãƒãƒ¼ãƒ Yã®åˆè¨ˆ 4 試åˆã®å¯¾æˆ¦ã ã£ãŸãŒï¼Œä¸€æ–¹çš„ãªå±•é–‹ã¨ãªã‚Šï¼Œå…¨è©¦åˆã§ãƒãƒ¼ãƒ XãŒå‹åˆ©ã—ãŸï¼Ž ã—ã‹ã‚‚,4 試åˆã‚’通ã˜ãŸXã®åˆè¨ˆå¾—点㯠33 点ã ã£ãŸã®ã«å¯¾ã—,Yã®åˆè¨ˆå¾—点ã¯ãŸã£ãŸã® 4 点ã ã£ãŸï¼Ž
ã‚ã¾ã‚Šã«ä¸€æ–¹çš„ãªå†…容ã®ãŸã‚,試åˆå†…容ã¸ã®èˆˆå‘³ãŒè–„ã‚Œã¦ã—ã¾ã£ãŸOã•ã‚“ã¯ï¼Œè©¦åˆã‚’観戦ã—ã¦ã„る間も競技プãƒã‚°ãƒ©ãƒŸãƒ³ã‚°ã®ä½œå•ãƒã‚¿ã‚’ã¤ã„ã¤ã„考ãˆã¦ã—ã¾ã£ã¦ã„ãŸï¼Ž ãã®ç”²æ–ã‚‚ã‚ã£ã¦ï¼ŒOã•ã‚“ã¯ä»¥ä¸‹ã®ã‚ˆã†ãªå•é¡Œã‚’æ€ã„ã¤ã„ãŸï¼Ž
野çƒãƒãƒ¼ãƒ Xã¨YãŒå¯¾æˆ¦ã—,XãŒå‹ã£ãŸè©¦åˆæ•°ï¼ŒYãŒå‹ã£ãŸè©¦åˆæ•°ï¼Œå¼•ã分ã‘ã®è©¦åˆæ•°ãŒãã‚Œãžã‚Œ A, B, C 試åˆã ã£ãŸã¨ã™ã‚‹ï¼Ž ã¾ãŸï¼Œå…¨ A+B+C 試åˆã‚’通ã˜ãŸX,Yã®ç·å¾—点ã¯ï¼Œãã‚Œãžã‚Œ SX 点,SY 点ã ã£ãŸã¨ã™ã‚‹ï¼Žå¾—点ã¯å…¨ã¦ 0 以上ã®æ•´æ•°ã§ã‚る. Xã¨YãŒåˆè¨ˆ A+B+C 試åˆå¯¾æˆ¦ã—ãŸã¨ã,全試åˆã®çµæžœã¨ã—ã¦ã“ã®ã‚ˆã†ãªæ¡ä»¶ã‚’満ãŸã™å„試åˆã®ã‚¹ã‚³ã‚¢ã®ä¸¦ã³ã¯ä½•é€šã‚Šæœ‰ã‚Šå¾—ã‚‹ã ã‚ã†ã‹ï¼Ÿ
ã“ã“ã§ï¼Œã‚る試åˆã§å‹åˆ©ã™ã‚‹æ¡ä»¶ã¯ï¼Œãã®è©¦åˆã«ãŠã‘る得点ãŒï¼Œç›¸æ‰‹ãƒãƒ¼ãƒ ã®å¾—点よりも多ã„ã“ã¨ã§ã‚り,ç‰ã—ã„å ´åˆã¯å¼•ã分ã‘ã¨ãªã‚‹ï¼Ž
ã¾ãŸï¼Œå„試åˆã®ã‚¹ã‚³ã‚¢ã®ä¸¦ã³ã‚’求ã‚る際,対戦ã—ãŸå…¨è©¦åˆã®çµæžœã‚’比ã¹ãŸæ™‚,Xã¨Yã®å¾—点ã®çµ„ã¿åˆã‚ã›ãŒåŒã˜ã§ã‚‚,ãã®é †åºãŒç•°ãªã‚Œã°åŒºåˆ¥ã™ã‚‹å¿…è¦ãŒã‚る. 例ãˆã°ï¼ŒXã¨Y㌠2 試åˆå¯¾æˆ¦ã—ãŸçµæžœï¼Œå…±ã« 1 å‹ãšã¤ã—,引ã分ã‘ãŒç„¡ã,Xã¨Yã®ç·å¾—点ãŒå…±ã« 1 点ãšã¤ã ã£ãŸã¨ã™ã‚‹ï¼Ž ã“ã®å ´åˆï¼Œå„試åˆã«ãŠã‘ã‚‹X,Yã®å¾—点を (Xã®å¾—点) - (Yã®å¾—点) ã¨ã„ã†è¡¨è¨˜ã§è¡¨ã—,åˆè¨ˆ 2 試åˆã®çµæžœã‚’並ã¹ã‚‹ã¨ï¼Œä»¥ä¸‹ã® 2 通りãŒä¸Žãˆã‚‰ã‚ŒãŸæ¡ä»¶ã‚’満ãŸã™ï¼Ž
試åˆã®é †åºã‚’区別ã—ã¦æ•°ãˆã‚‹ã®ã§ï¼Œã“れらã¯åŒºåˆ¥ã•ã‚Œã‚‹ï¼Ž
ã‚ãªãŸã«ã¯ã“ã®ç”ãˆã‚’求ã‚るプãƒã‚°ãƒ©ãƒ を作ã£ã¦æ¬²ã—ã„. ãŸã ã—,求ã‚ã‚‹æ•°ã¯ã¨ã¦ã‚‚大ãã„æ•°ã«ãªã‚Šå¾—ã‚‹ãŸã‚,求ã‚ã‚‹æ•°ã‚’ 1,000,000,007 ã§å‰²ã£ãŸä½™ã‚Šã‚’ç”ãˆã‚‹ã‚ˆã†ã«ã—ã¦æ¬²ã—ã„.
入力ã¯è¤‡æ•°ã®ãƒ‡ãƒ¼ã‚¿ã‚»ãƒƒãƒˆã‹ã‚‰ãªã‚‹ï¼Ž å„データセット㯠1 è¡Œã‹ã‚‰ãªã‚Šï¼Œæ¬¡ã®å½¢å¼ã§è¡¨ã•ã‚Œã‚‹ï¼Ž
A B C SX SY
ã“ã“ã§ï¼ŒA ã¯ãƒãƒ¼ãƒ Xã®å‹åˆ©æ•°ï¼ŒB ã¯ãƒãƒ¼ãƒ Yã®å‹åˆ©æ•°ï¼ŒC ã¯å¼•ã分ã‘ã®è©¦åˆæ•°ï¼ŒSX ã¯ãƒãƒ¼ãƒ Xã®ç·å¾—点,SY ã¯ãƒãƒ¼ãƒ Yã®ç·å¾—点を表ã™ï¼Ž A, B, C, SX, SY ã¯å…¨ã¦ 0 以上 1,000,000 以下ã®æ•´æ•°ã§ã‚り,ã‹ã¤ 0 < A+B+C を満ãŸã™ï¼Ž
入力ã®çµ‚ã‚ã‚Šã¯ï¼Œ5 ã¤ã®ã‚¼ãƒã‹ã‚‰ãªã‚‹è¡Œã§ç¤ºã•ã‚Œã‚‹ï¼Ž
å„データセットã«ã¤ã„ã¦ï¼Œä¸Žãˆã‚‰ã‚ŒãŸæ¡ä»¶ã‚’満ãŸã™å ´åˆã®æ•°ã‚’ 1,000,000,007 ã§å‰²ã£ãŸä½™ã‚Šã®ã¿ã‹ã‚‰ãªã‚‹è¡Œã‚’ 1 è¡Œã§å‡ºåŠ›ã›ã‚ˆï¼Ž
1 1 0 1 1 0 0 2 3 2 4 0 0 33 4 5 4 2 20 25 4726 87361 2742 23497 162843 328324 420923 12782 834286 538297 0 0 0 0 0
2 0 114660 512095631 673703234 166259450