There are N black checker pieces on the coordinate plane. The i-th checker piece is located at point . You are playing a new type of game with these checker pieces. A move is defined as follows : - Place a white checker piece W at some coordinate where x, y are integers. While there exist a black checker piece B at distance exactly 1 from W, you may choose to capture B by moving W to the symmetric point of its current position with respect to B, and remove B. Note that multiple checker pieces may occupy the same point at the same time. Once no such operation is possible or you choose to stop performing such operation, W is removed. Each black checker piece has a 1/2 probability of getting removed before the game starts. What is the expected minimum number of moves required to complete the game?
There are N black checker pieces on the coordinate plane. The i-th checker piece is located at point (Xi,Yi)(X_{i}, Y_{i})(Xi,Yi). You are playing a new type of game with these checker pieces. A move is defined as follows : - Place a white checker piece W at some coordinate (2x, y) where x, y are integers. While there exist a black checker piece B at distance exactly 1 from W, you may choose to capture B by moving W to the symmetric point of its current position with respect to B, and remove B. Note that multiple checker pieces may occupy the same point at the same time. Once no such operation is possible or you choose to stop performing such operation, W is removed. Each black checker piece has a 1/2 probability of getting removed before the game starts. What is the expected minimum number of moves required to complete the game? Let E be this expected value. It can be proven that E⋅2NE cdot 2^{N}E⋅2N is an integer. Output E⋅2N mod 1000000007E cdot 2^{N} bmod 1000000007E⋅2Nmod1000000007
