問題文
注重健康的高桥决定服用网上购买的补充剂。
补充品 N 可用, 编号至1 它们的编号最大为 N 。
另外,补充剂的味道是 M 有不同的类型, 编号至1 它们的编号最大为 M 。补品 i (1 ≦ i ≦ N) 的味道是 f_i (1 ≦ f_i ≦ M) 。
高桥计划在多天内按数字顺序服用补充剂。高桥服用补充剂,这样他就不会懈怠。 1 如果剩余多于一个,请务必 1 我们制定了一条规则,您必须至少服用一种补充剂。
高桥身体强壮,所以1 一天服用多少补充剂并不重要,但你会对相同的味道感到厌倦,所以最好在同一天服用相同口味的补充剂。 2 不能携带超过 1 个。
高桥先生想知道在这种情况下总共有多少种补充品的服用方式,以便考察服用补充品的利弊。
这里 2 不同的摄入方法被定义为在给定日期服用的补充剂数量的不同组合。
入力
输入将以以下格式从标准输入提供。
N M f_1 f_2 : f_N
- 1 第几行包含,2 整数 N (1 ≦ N ≦ 100,000) 和 M (1 ≦ M ≦ 100,000) 用空格分隔。这是一个补充 N 有不同口味可供选择。 M 表示有不同类型。
- 2 从行 N 行提供有关补充剂味道的信息。这些 N 从行顶部开始 i (1 ≦ i ≦ N) 行是一个整数 写入 f_i (1 ≦ f_i ≦ M) 。这是一个补充 i 的味道 如果您对 f_i 。
部分点
针对此问题设置了部分分数。
- N ≦ 5,000 和 所有满足 M ≦ 5,000 的数据集 如果您正确回答 1 的回答正确,除上述之外, 30 点。 如果您正确回答
- 没有附加约束的数据集 2 的回答正确,除上述之外, 70 点。 如果您正确回答
出力
摄入方法总数 除以 1,000,000,007 (= 1000000007) 后的余数 在 1 行输出。还在输出末尾添加换行符。
入力例1
5 2 1 2 1 2 2
出力例1
5
下面 可以考虑 5 。
| 1 日目 | 2 日目 | 3 日目 | 4 日目 | 5 日目 |
| 补充品 1 | 补充品 2 | 补充品 3 | 补充品 4 | 补充品 5 |
| 补充品 1 | 补充品 2 | 补充品 3,4 | 补充品 5 | 无 |
| 补充品 1 | 补充品 2,3 | 补充品 4 | 补充品 5 | 无 |
| 补充品 1,2 | 补充品 3 | 补充品 4 | 补充品 5 | 无 |
| 补充品 1,2 | 补充品 3,4 | 补充品 5 | 无 | 无 |
入力例2
6 6 1 2 3 4 5 6
出力例2
32
怎么吃都吃不腻。