← 返回题目列表

AtCoder · abc017_4

D. 补充品

中文机器翻译题面 查看原题

問題文

注重健康的高桥决定服用网上购买的补充剂。

补充品 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

怎么吃都吃不腻。