Lucy is playing a game named . The game is played on an infinite two-dimensional plane. At the beginning, every grid point has exactly one cell, while other points are empty.

Lucy will play the game for seconds. During each second, every cell divides itself into copies and the copies then spread. Assume that a cell locates at point at the start of the second, and at the end of the second, its copies will locate at coordinates respectively. The original cell completes its life mission and disappears.

Assume that the cells will reproduce following the above rules second by second. Lucy wants to know that, if everything goes on well, how many cells will be at the coordinate at the end of the -th second. As the answer may be enormous, you just need to print it modulo .