Mr. Panda likes creating and solving mathematical puzzles. One day, Mr. Panda came up with a puzzle when he was playing dominoes.In a grid that consists of an infinite number of rows and columns, all
Mr. Panda likes creating and solving mathematical puzzles. One day, Mr. Panda came up with a puzzle when he was playing dominoes.In a grid that consists of an infinite number of rows and columns, all cells are white except Nmathbf{N}N given cells which are colored black. Mr. Panda wants to know how many dominoes there are in the gird.A domino is a rectangle that meets the following requirements. The domino is formed of a continuous subset of the rows and columns of the grid. The domino has at least 1{1}1 row and 1{1}1 column. The cells on the edge of the domino are black. It means the topmost row, the bottommost row, the leftmost column and the rightmost column only consist of black cells. The aspect ratio of the domino is 2:1{2:1}2:1 or 1:2{1:2}1:2. It means, if the domino has k{k}k columns, it should have either 2k{2k}2k rows or k2frac{k}{2}2k rows (k{k}k is an even number in this case). For example, in the chart below, the 3×33 times 33×3 grid on the left contains 6{6}6 dominos (4{4}4 dominos of 1×21 times 21×2 and 2{2}2 dominos of 2×12 times 12×1), and the 3×63 times 63×6 grid on the right contains 15{15}15 dominos (10{10}10 dominos of 1×21 times 21×2, 4 dominos of 2×12 times 12×1 and a domino of 3×63 times 63×6). Because the grid is huge, Mr. Panda is too lazy to count the number of dominoes. Could you please help Mr. Panda find how many dominoes there are in the gird?