1130. Number of Ways to Reach a Position After K Steps

You start at integer position startPos on a number line and must take exactly k steps, each moving one unit left or right. Return the number of distinct ways to arrive at endPos after exactly k steps, taken modulo 1000000007. The input is JSON {startPos, endPos, k}.

Input: JSON {startPos, endPos, k}.

Output: Integer — the number of ways modulo 1e9+7.

Examples

Input: {"startPos":1,"endPos":2,"k":3}
Output: 3
Explanation: Three step sequences end at 2.

Input: {"startPos":2,"endPos":5,"k":10}
Output: 0
Explanation: Parity makes it impossible.

Input: {"startPos":0,"endPos":0,"k":0}
Output: 1
Explanation: Already there.

Constraints

• 1<=k<=1000

Asked by