[ARC174] E - Existence Counting

E - Existence Counting

Time Limit: 4 sec / Memory Limit: 1024 MB

分数: 700 分

题面

给定整数 和 。考虑一个长度为 的序列 ，满足以下所有条件:

• 是整数，满足 。
• 中的所有元素都不相同。

我们按字典序排列所有可能的序列 ，形成一个“序列的序列”，称为字典 。

给定一个存在于字典 中的序列 ，对于每个整数 ，回答以下问题:

• 找到满足以下所有条件的序列 的数量，取模 ：
  • 序列 存在于字典 中。
  • 整数 包含在序列 中。
  • 序列 按字典序小于或等于序列 。

什么是字典序的序列？ 如果且仅如果满足以下条件1或2，则序列 比序列 字典序小:

1. 并且 。
2. 存在一个整数 满足以下两个条件:

限制条件

• 所有输入值都为整数。
• 满足题面中的条件。

---

输入

输入以以下格式从标准输入给出：

输出

共输出 行。
第 行应该包含整数 的问题的答案。

---

样例输入 1

4 2
3 2

样例输出 1

5
5
4
2

在这个样例输入中，。
这里，字典 是
。

在字典 中，比序列 字典序小于或等于的序列中，

• 有五个序列包含 ：，
• 有五个序列包含 ：，
• 有四个序列包含 ：，
• 有两个序列包含 ：。

---

样例输入 2

18 13
5 13 11 2 18 1 10 15 17 4 12 7 3

样例输出 2

925879409
905921009
665544804
665544719
783035803
349952762
349952758
349952757
349952757
349921178
212092637
710350150
378895603
129113201
129111892
129098081
129096772
110181652