Problem #58
Circle of Death
Let n be 10 times the largest integer which cannot be represented as the sum of five non-zero perfect squares. Now, consider yourself standing in a circle of n people (positioned 1 to n around the circle), where every k^{th} (k = 10) person is killed from the remaining ones standing except the last one. For example, if n = 4 and k = 2, then the order in which people will be killed is 2, 4, 3. Hence person at position 1 will be the survivor.
Let p be the position you will choose so as to survive this game (be the last to be killed). Also, for n = 40, let q be the smallest value of k (>1) for which people are killed in the same order as they are standing (i.e. 1, 2, 3,...).
What is (p * q)\mod{1000000009}?