\(N=2005, M=2003\) とします（\(M\) は素数で \(N=M+2\)）．

最後の bounding box の大きさは \(1 \pmod{M}\) なので，途中がすべて \(0\) または \(1\) になるようなものの数え上げを調整します．

bounding box の \(y\) 方向の幅の列を作ります．次の形で作りました．

\[(0,a_1,a_1,a_2,a_2,\ldots,a_k,a_k,N-1,N-1,N-1,\ldots,N-1)\]

さらに \(a_i\) は \(a^{-1}\bmod M\) が単調増加になるという縛りを付けます．具体的には \(i^{-1}\bmod M\) を並べた列の LIS をとって，その \(k\) 元部分集合を選ぶようにすればよいです．\(b_i=a_i^{-1}\bmod M\) とすると，途中の \(x\) 方向の幅としては，\(b_i\) または \(M\) が許容されるという \(2\) 状態の dp になります．

これで十分多様性があるので，あとは meet in the middle の解法になるようにします．

\(k=34\) ととり，\(a_i\) の候補を \(68\) 個用意して，前後半用の \(34\) 個ずつに分けておき，前半用と後半用の \(a_i\) から \(17\) 個ずつ選ぶという形で AC が得られました．

• 解答例：https://atcoder.jp/contests/jsc2025-final/submissions/68717587