快看!动物园里的袋鼠正在表演套娃节目!
有 n 只袋鼠,第 i 只袋鼠身体的体积是 Ai,口袋的容积是 Bi(始终有 Ai>Bi)。称袋鼠 i 可以被放入袋鼠 j 的口袋里(即有序对 (i,j) 满足“套娃”条件),当且仅当:
- Ai<Bj
- 袋鼠 i 现在不在任何袋鼠的口袋里
- 袋鼠 j 的口袋现在不包含任何袋鼠
刚开始,袋鼠们站在一排,没有相互嵌套。它们会不断选出满足套娃条件的一对袋鼠 (i,j),之后袋鼠 i 会跳进袋鼠 j 的口袋里。这个操作不断进行,直至无法选出满足套娃条件的一对袋鼠为止。(注意,如果袋鼠 i 直接或间接地包含其他袋鼠,这些袋鼠也会和 i 一块运动。被包含的袋鼠不会增加袋鼠 i 的体积)
由于可能某一时刻袋鼠对的选择不是唯一的,袋鼠们可以选择其中的任意一对,这就导致了可能会有很多种最终袋鼠嵌套的方案。yd 十分好奇会有多少种不同的方案,可是他数不过来,于是求助于你。由于方案数量可能很多,你只需要告诉他方案数量对 109+7 取模后的值即可。