P4184 [USACO18JAN] Sprinklers P

农夫约翰有块田，这块田可视为一个 $N×N$ 的正方形网格。西南角为 $(0,0)$ ，东北角为 $(N-1, N-1)$ 。 在某些格子中有双头喷头，每一个都能够同时喷洒水和肥料。一个位于 $(i,j)$ 的双头喷头会 * 将水洒在所有满足 $N≥x≥i,$ $N≥y≥j$ 的格子 $(x,y)$ 上； * 将肥料洒在所有满足 $0≤x≤i$ 和 $0≤y≤j$ 的格子 $(x,y)$ 上。 农民约翰想在这块田里切割出一个矩形种甜玉米。矩形的边不能把格子切开。矩形内的所有格子都必须能由双头喷头灌溉和施肥。 求切割矩形的方案数。由于这个数字可能很大，所以输出对 $10^9+7$ 取模。

无

无