First of all, you are given a positive integer k. There are n soldiers on the plane, whose coordinates , . . . , satisfy k ≤ ai , bi ≤ 0 and ai + bi = k. Moreover, n castles, whose coordinates , . . . , satisfy 0 ≤ ci , di ≤ k and ci + di = k, are on the plane. Now, every soldier needs to choose a castle and leave for it. For every step, the soldier located at can go to or . 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 109 + 7.
First of all, you are given a positive integer k(k ≤ 105 ). There are n(1 ≤ n ≤ 200) soldiers on the plane, whose coordinates (a1, b1), . . . ,(an, bn) satisfy −k ≤ ai , bi ≤ 0 and ai + bi = −k. Moreover, n castles, whose coordinates (c1, d1), . . . ,(cn, dn) satisfy 0 ≤ ci , di ≤ k and ci + di = 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 109 + 7.
