# Solution of;
# Project Euler Problem 649: Low-Prime Chessboard Nim
# https://projecteuler.net/problem=649
# 
# Alice and Bob are taking turns playing a game consisting of $c$ different 
# coins on a chessboard of size $n$ by $n$. The game may start with any 
# arrangement of $c$ coins in squares on the board. It is possible at any time 
# for more than one coin to occupy the same square on the board at the same 
# time. The coins are distinguishable, so swapping two coins gives a different 
# arrangement if (and only if) they are on different squares. On a given turn, 
# the player must choose a coin and move it either left or up $2$, $3$, $5$, 
# or $7$ spaces in a single direction. The only restriction is that the coin 
# cannot move off the edge of the board. The game ends when a player is unable 
# to make a valid move, thereby granting the other player the victory. 
# Assuming that Alice goes first and that both players are playing optimally, 
# let $M(n, c)$ be the number of possible starting arrangements for which 
# Alice can ensure her victory, given a board of size $n$ by $n$ with $c$ 
# distinct coins. For example, $M(3, 1) = 4$, $M(3, 2) = 40$, and $M(9, 3) = 
# 450304$. What are the last $9$ digits of $M(10\,000\,019, 100)$?
# 
# by lcsm29 http://github.com/lcsm29/project-euler
import timed


def dummy(n):
    pass


if __name__ == '__main__':
    n = 1000
    i = 10000
    prob_id = 649
    timed.caller(dummy, n, i, prob_id)
