Statement

Peter is standing at the origin of the Cartesian plane, and he decided to take a regular walk to point (N, M) for some positive integers N and M. In each step of a regular walk, Peter must move parallel to one of the axes. During a move, he can go either one unit to the right or one unit up. Formally, a regular walk from (0, 0) to (N, M) is a sequence of points (x_i, y_i) (0 ≤ i ≤ N + M) such that (1) (x_0, y_0) = (0, 0) and (x_N+M, y_N+M) = (N, M), and (2) for each i = 1, …, N+M, either (x_i, y_i) = (x_i-1 + 1, y_i-1) or (x_i, y_i) = (x_i-1, y_i-1 + 1). We define the area under a regular walk as the area of the polygon whose vertices in clockwise order are (0, 0) = (x_0, y_0), (x_1, y_1), …, (x_N+M, y_N+M) = (N, M) and (N, 0). Given a prime number P and a remainder R, you have to find the number W of regular walks from (0, 0) to (N, M) under which the area is congruent to R modulo P. Since the answer can be very large, you have to compute it modulo 10^9 + 7.