某一天，小 M 学习了一个叫做「分数规划」的算法，它是用来解决「分数规划问题」的。
:::info[分数规划问题]{open}
有 个物品，第 个物品的价值为 ，重量为 。 均为正整数。
从 个物品中选出 个，记所选物品为 ，最大化
的值。
:::
恰巧，小 M 还做过一道叫做 sale 的题。他突发奇想，便出了一道题来考考你。
给定 ，以及物品的价值序列 ，求有多少种物品的重量序列 ，满足 ，使以下贪心策略恰好求得「分数规划问题」的最优解：
- 将物品 按价值 降序排序。对于价值相同的物品，按序号 升序排序。选取排序后的前 个物品。
答案对 取模。
