← 返回题目列表

AtCoder · exawizards2019_d

D. 模运算

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

分数: 600 点

问题陈述

Snuke 有一块黑板和一套 S 组成 N 整数。 的 i- 第一个元素 S is S_i.

他写了一个整数 黑板上的 X ,然后执行以下操作 N 次:

  • 从以下位置选择一个元素 S 并将其删除。
  • 让 x 是现在写在黑板上的数字,并且 y 是从 S。将黑板上的数字替换为 x \bmod {y}.

有 N! 元素被删除的可能顺序 S。 对于每一个,找出将写在黑板上的数字 N 操作,并计算所有这些的总和 N! 数字取模 10^{9}+7.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 200
  • 1 \leq S_i, X \leq 10^{5}
  • S_i 两两不同。

输入

输入由标准输入按以下格式给出:

N X
S_1 S_2 \ldots S_{N}

输出

打印答案。


示例输入 1

2 19
3 7

示例输出 1

3
  • 我们有两种可能的顺序来删除数字 S.
  • 如果我们删除 3 和 7 按照这个顺序,黑板上的数字变化如下: 19 \rightarrow 1 \rightarrow 1.
  • 如果我们删除 7 和 3 按照这个顺序,黑板上的数字变化如下: 19 \rightarrow 5 \rightarrow 2.
  • 输出应该是以下各项的总和: 3.

示例输入 2

5 82
22 11 6 5 13

示例输出 2

288

示例输入 3

10 100000
50000 50001 50002 50003 50004 50005 50006 50007 50008 50009

示例输出 3

279669259
  • 请务必计算总和模 10^{9}+7.