While the Big Jarab was preparing the tasks for admission in the quest for the Sacred Ino, Talb found a shorter way. He is sure that the building in which the Sacred Ino is kept has a back door, and he also knows that he only has to pass through N distinct cities to get there from his initial position.

We can model Talb's world as an infinite grid, where each square represents a city and he can get from any city to the cities situated to the East, West, North or South of his current location. After he starts his journey, Talb will only pass through a neighbouring city if he hasn't passed through it before.

Now, Talb is wondering how many different ways there are to make such journeys. If we can perform a translation operation over a path (to either of the four possible directions) and get another possible path for the journey, then the paths will only be counted once. In other words, the paths: North, North, North and South, South, South are the same, as we can overlap the two paths performing a translation (either the first path to the south, either the second one to the north).


N, the number of cities.


The number of distinct possible paths.


  • 1 ≤ N ≤ 13


22The only two possible paths from the initial position are: North and East. Other paths are translations of these.
36The six paths are in shape of: a vertical bar, an horizontal line, and the four possible rotations of a L-shape, all made of three cubes.

Sponsors Gold