First of all, you are given a positive integer k(k ≤ 10⁵ ). There are n(1 ≤ n ≤ 200) soldiers on the plane, whose coordinates (a₁, b₁), . . . ,(a_n, b_n) satisfy −k ≤ a_i , b_i ≤ 0 and a_i + b_i = −k. Moreover, n castles, whose coordinates (c₁, d₁), . . . ,(c_n, d_n) satisfy 0 ≤ c_i , d_i ≤ k and c_i + d_i = k, are on the plane.

Now, every soldier needs to choose a castle and leave for it. For every step, the soldier located at (x, y) can go to (x+ 1, y) or (x, y+ 1). In order to avoid stampedes, we require that the paths of any two soldiers should not intersect, including the starting and ending points. Furthermore, any soldier cannot go above y −x = k or beneath y −x = −k. Calculate how many ways the can walk, and output the answer modulo 10⁹ + 7.