UVA 11486 – Finding Paths in Grid

Given a grid of N rows and 7 columns. Initially there are 4 players in the first row (the column location will be given as input). A player can only move diagonally to the next row. For example, a player in row-3 column-4 or (3, 4) has two valid moves: (4, 3) and (4,5). But the player in (3, 1) has only one valid move, which is (4,2). Each cell can be visited by at most one player.

Count in how many ways all of the players can reach row N (1 ≤ N ≤ 1000000000) and mod the output by 1000000007.