Percy would like to become the Penguin Emperor. First, he must go on a long journey to prove himself worthy.
There are several cities in Penguin Empire.
All the cities lie on a circle around the great mountain.
The cities are numbered 0 through numCities-1 in the clockwise direction around the mountain.
Percy lives in city 0 and that is where he will begin his journey. On the first day he will travel to a city adjacent to city 0. On the second day he will travel to another city two cities away from his current city. And so on: for each k, on the k-th day he will travel to a new city k cities away. Each day, Percy can choose a new direction of travel: either clockwise or counter-clockwise around the mountain.
You are given the int numCities representing the number of cities in the Penguin Empire. You are also given a long daysPassed representing the number of days that have passed since Percy's journey began. Compute and return the number of journeys that take daysPassed days and return home to city 0. Two journeys are considered different if there is some k such that after k days the traveler is in different cities. As the number of journeys can be quite large, please return the result modulo 1,000,000,007.