座標平é¢ä¸Šã®åŽŸç‚¹$O$を左下ã€åº§æ¨™$(W,H)$ã«ã‚る点をå³ä¸Šã¨ã™ã‚‹é•·æ–¹å½¢ã®é ˜åŸŸãŒä¸Žãˆã‚‰ã‚Œã¦ã„ã¾ã™ã€‚ã“ã®é ˜åŸŸã«å«ã¾ã‚Œã‚‹ã€$x$座標ã¨$y$座標ãŒã¨ã‚‚ã«æ•´æ•°ã§ã‚る点を3個以上å«ã‚€ç‚¹ã®é›†ã¾ã‚Šã‚’考ãˆã¾ã™ã€‚ã“ã®ã‚ˆã†ãªç‚¹ã®é›†ã¾ã‚Šã®ã™ã¹ã¦ã®çµ„ã¿åˆã‚ã›ã®å€‹æ•°ã‚’$N$ã¨ã—ã€ç‚¹ã®é›†ã¾ã‚Šã®ãã‚Œãžã‚Œã‚’$D_1, D_2, ..., D_N$ã§è¡¨ã—ãŸã¨ãã€$D_1, D_2, ..., D_N$ã®ãã‚Œãžã‚Œã«å«ã¾ã‚Œã‚‹ç‚¹ã‚’é ‚ç‚¹ã¨ã™ã‚‹ä¸‰è§’形を考ãˆã¾ã™ã€‚
ãŸã¨ãˆã°ã€å›³ã®ã‚ˆã†ã«$W=H=1$ã®ã¨ãã€ç‚¹$O(0,0)$ã€$A(1,0)$ã€$B(1,1)$ã€$C(0,1)$ã®ã†ã¡ã€ï¼“個以上å«ã‚€ç‚¹ã®é›†ã¾ã‚Šã¯$\{O,A,B\}$ã€$\{O,A,C\}$ã€$\{O,B,C\}$ã€$\{A,B,C\}$ã€$\{O,A,B,C\}$ã®ï¼•ã¤ã§ã™ã€‚ã“ã®ä¾‹ã®å ´åˆã€ç‚¹ã®é›†ã¾ã‚Šã®ãã‚Œãžã‚Œã«å«ã¾ã‚Œã‚‹ä¸‰è§’å½¢ã¯æ¬¡ã®ã‚ˆã†ã«ãªã‚Šã¾ã™ã€‚
ã“ã®ä¾‹ã‹ã‚‰ã‚ã‹ã‚‹ã‚ˆã†ã«ã€åŒã˜ä¸‰è§’å½¢ãŒï¼’ã¤ä»¥ä¸Šã®ç‚¹ã®é›†ã¾ã‚Šã«å«ã¾ã‚Œã‚‹å ´åˆãŒã‚ã‚Šã¾ã™ã€‚ãŸã¨ãˆã°ã€ä¸‰è§’å½¢$OAB$ã¯ç‚¹ã®é›†ã¾ã‚Š$\{O,A,B\}$ã«ã‚‚$\{O,A,B,C\}$ã«ã‚‚å«ã¾ã‚Œã¾ã™ã€‚
$W$ã¨$H$ãŒä¸Žãˆã‚‰ã‚Œã‚‹ã€‚点ã®é›†ã¾ã‚Š$D_1, D_2, ..., D_N$ãã‚Œãžã‚Œã«å«ã¾ã‚Œã‚‹ç‚¹ã‚’é ‚ç‚¹ã¨ã™ã‚‹ä¸‰è§’å½¢ã®å€‹æ•°ã‚’$t_1, t_2, ..., t_N$ã¨ã™ã‚‹ã¨ãã€ä¸‰è§’å½¢ã®å€‹æ•°ã®å’Œ$t_1+t_2+...+t_N$を計算ã™ã‚‹ãƒ—ãƒã‚°ãƒ©ãƒ を作æˆã›ã‚ˆã€‚
入力ã¯ä»¥ä¸‹ã®å½¢å¼ã§ä¸Žãˆã‚‰ã‚Œã‚‹ã€‚
$W$ $H$
1行ã«$W$ã¨$H$ ($1 \leq W,H \leq 1,000$)ãŒä¸Žãˆã‚‰ã‚Œã‚‹ã€‚
ãã‚Œãžã‚Œã®ç‚¹ã®é›†ã¾ã‚Šã«å«ã¾ã‚Œã‚‹ä¸‰è§’å½¢ã®å€‹æ•°ã®å’Œã‚’1,000,000,007ã§å‰²ã£ãŸä½™ã‚Šã‚’1行ã«å‡ºåŠ›ã™ã‚‹ã€‚
1 1
8
1 2
144
100 100
879128399