Problem:


Score : 600 points

Problem Statement

Snuke has a blackboard and a set S consisting of N integers.
The i-th element in S is S_i.

He wrote an integer X on the blackboard, then performed the following operation N times:

Choose one element from S and remove it.

Let x be the number written on the blackboard now, and y be the integer removed from S. Replace the number on the blackboard with x \bmod {y}.

There are N! possible orders in which the elements are removed from S.
For each of them, find the number that would be written on the blackboard after the N operations, and compute the sum of all those N! numbers modulo 10^{9}+7.

Constraints

All values in input are integers.

1 \leq N \leq 200

1 \leq S_i, X \leq 10^{5}

S_i are pairwise distinct.

Input

Input is given from Standard Input in the following format:

N X
S_1 S_2 \ldots S_{N}

Output

Print the answer.

Sample Input 1

2 19
3 7

Sample Output 1

3

There are two possible orders in which we remove the numbers from S.

If we remove 3 and 7 in this order, the number on the blackboard changes as follows: 19 \rightarrow 1 \rightarrow 1.

If we remove 7 and 3 in this order, the number on the blackboard changes as follows: 19 \rightarrow 5 \rightarrow 2.

The output should be the sum of these: 3.

Sample Input 2

5 82
22 11 6 5 13

Sample Output 2

288

Sample Input 3

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

Sample Output 3

279669259

Be sure to compute the sum modulo 10^{9}+7.



Sample input:
2 19
3 7


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())

S = list(map(int,input().split()))

mod = 10**9+7
fact = [1]
for n in range(1, N+1):
    fact.append( fact[-1] * n % mod)
from copy import deepcopy as dcpy

def solve(S, X):
    n = len(S)

    if all( X < s for s in S):
        return fact[n] * X % mod
    if n == 1:
        return X % S[0] % mod

    ans = 0

    s_holder = [ dcpy(S) for _ in range(n)]
    for i,s in enumerate(S):
        new_x = X % s
        s_holder[i].pop(i)
        ans = (ans + solve(s_holder[i], new_x)) % mod
    return ans % mod

print( solve(S, X) % mod )

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, X = map(int, input().split())
S = list(map(int, input().split()))
ans_lst = []
for tpl in itertools.permutations(S):
    x = X
    for y in tpl:
        x = x % y
    ans_lst.append(x)

print(sum(ans_lst) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N, X = map(int, input().split())
S = list(map(int, input().split()))
 
l = list(itertools.permutations(S))
 
ans = 0
for i in range(len(l)):
    x = X
    for j in range(len(S)):
        if x >= l[i][j]:
            x %= l[i][j]
    ans += x % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, x = map(int, input().split())
s = map(int, input().split())
tmp = 0
m = 10 ** 9 + 7
p = list(itertools.permutations(s))

for i in range(len(p)):
  y = x
  for j in range(len(p[i])):
    y = y % p[i][j]

  tmp += y

print(tmp % m)

Submission status: Time Limit Exceeded

Solution code:
import itertools

a = [int(each) for each in input().split()]

N = a[0]
X = a[1]

S = set(int(each) for each in input().split())

ans = 0

for s in itertools.permutations(S):
    x = X

    m = 0
    for v in s:
        if m > v:
            continue
        else:
            x = x % v
    ans += x

ans = ans % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations as perm

n, x = map(int, input().split())
s = list(map(int, input().split()))

s_list = list(perm(s))
sum = 0

for i in range(len(s_list)):
    x_i = x
    for j in range(len(s_list[i])):
        x_i = x_i % s_list[i][j]
    sum += x_i

print(sum % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,x = LI()
    a = sorted(LI(), reverse=True)
    d = collections.defaultdict(int)
    d[(x,0)] = 1

    fm = {}
    def f(i):
        if i < 2:
            return 1
        if i in fm:
            return fm[i]
        r = i * f(i-1) % mod
        fm[i] = r
        return r

    for ai in range(n):
        c = a[ai]
        e = collections.defaultdict(int)
        for kk,v in d.items():
            k,i = kk
            if ai < n-1:
                e[(k,i+1)] += v
                e[(k,i+1)] %= mod
            kc = k % c
            e[(kc,i)] += v
            e[(kc,i)] %= mod
            for j in range(i-1,-1,-1):
                e[(kc,j)] += v * f(i) // f(j)
                e[(kc,j)] %= mod
        d = e

    r = 0
    for kk,v in d.items():
        k,i = kk
        if i > 0:
            continue
        r += k * v
        r %= mod

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
import itertools

a = [int(each) for each in input().split()]

N = a[0]
X = a[1]

S = set(int(each) for each in input().split())

ans = 0

for s in itertools.permutations(S):
    x = X
    for v in s:
        x = x % v
    ans += x

ans = ans % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, X = list(map(int, input().split()))
S = list(map(int, input().split()))

orders = itertools.permutations([x for x in range(N)])

ans = 0
for order in orders:
    x = X
    for selected in order:
        x = x%(S[selected])
    ans += x

print(ans%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import sys
# import bisect
# import math
import itertools
# import numpy as np
# import collections

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e, p = range, enumerate, print
    ip = IP()
    id = Idea()
    mod = 10 ** 9 + 7

    """この下から書いてね"""
    n, x = ip.IL()
    ans = 0
    for y in list(itertools.permutations(ip.IL())):
        res = x
        for z in y:
            res = res % z
        ans += res
    p(ans % mod)


main()

Submission status: Time Limit Exceeded

Solution code:

import copy
def select_s(X, remain_s):
    total = 0

    if len(remain_s) == 0:
        return X

    for i, s in enumerate(remain_s):
        tmp_s = copy.deepcopy(remain_s)
        tmp_x = X % int(tmp_s[i])
        del tmp_s[i]
        total += select_s(tmp_x, tmp_s)

    return total


N, X = input().split(' ')
X = int(X)
S = input().split(' ')
print(select_s(X, S) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n, x = input().split()

seq = input().split()

import itertools

array = []

for j in range(len(list(itertools.permutations(seq)))):
    array.append(list(itertools.permutations(seq))[j])


su = 0

for i in range(len(array)):
    c = int(x)
    for k in range(int(n)):
        y = c
        b = array[i][k]
        c = y % int(b)
    su += c

print(su)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, X = map(int,input().split())
S = list(map(int,input().split()))

mod = 10**9+7
res = 0
for per in permutations(S, N):
  board = X
  for p in per:
    board %= p
  res += board
print(res%mod)

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().strip().split(' '))
s = list(map(int,input().split()))
import itertools
black = 0
for v in itertools.permutations(s):
    xnew = x
    for i in range(n):
        xnew = xnew%v[i]
    black = black%1000000007+xnew
print(black%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import bisect
# import math
import itertools
# import numpy as np
# import collections

"""Template"""


class IP:
    """
    入力を取得するクラス
    """

    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: int
        """
        return int(self.input())

    def S(self):
        """
        1文字の取得(str
        :return: str
        """
        return self.input()

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]

    def SILS(self, n):
        """
        Some Int LineS
        横に複数、縦にも複数
        :param n: 行数
        :return: list
        """
        return [self.IL() for _ in range(n)]

    def SSLS(self, n):
        """
        Some String LineS
        :param n: 行数
        :return: list
        """
        return [self.SL() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if self.bit_o(i, j):
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val

    def S(self, s, r=0, m=-1):
        """
        ソート関係行います。色々な設定あります。
        :param s: 元となるリスト
        :param r: reversするかどうか 0=False 1=True
        :param m: （2次元配列）何番目のインデックスのソートなのか
        :return: None
        """
        r = bool(r)
        if m == -1:
            s.sort(reverse=r)
        else:
            s.sort(reverse=r, key=lambda x: x[m])

    def bit_n(self, a, b):
        """
        bit探索で使います。0以上のときにTrue出します
        自然数だからn
        :param a: int
        :param b: int
        :return: bool
        """
        return bool((a >> b & 1) > 0)

    def bit_o(self, a, b):
        """
        bit探索で使います。1のときにTrue出すよ
        oneで1
        :param a: int
        :param b: int
        :return: bool
        """
        return bool(((a >> b) & 1) == 1)

    def ceil(self, x, y):
        """
        Round up
        小数点切り上げ割り算
        :param x: int
        :param y: int
        :return: int
        """
        return -(-x // y)

    def ave(self, a):
        """
        平均を求めます
        :param a: list
        :return: int
        """
        return sum(a) / len(a)

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e, p = range, enumerate, print
    ip = IP()
    id = Idea()
    mod = 10 ** 9 + 7

    """この下から書いてね"""
    n, x = ip.IL()
    s = ip.IL()
    ans = 0
    o = list(itertools.permutations(s))
    for y in o:
        res = x
        for z in y:
            res = res % z
            if res == 1:
                break
        ans += res
    p(ans % mod)

main()

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().strip().split(' '))
s = list(map(int,input().split()))
import itertools
black = 0
for v in itertools.permutations(s, n):
    xnew = x
    for i in range(n):
        xnew = xnew%v[i]
    black = (black+xnew)%1000000007
print(black)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n, x = map(int, raw_input().split())
ss = map(int, raw_input().split())
m1 = {x: 1}
for i in range(n):
    m2 = {}
    for m in m1:
        for s in ss:
            v = m % s
            m2[v] = (m2.get(v, 0) + m1[m]) % MOD
        if i > 0:
            m2[m] = (m2.get(m, 0) - m1[m] * i) % MOD
    m1 = {m: m2[m] for m in m2 if m2[m] > 0}
ret = 0
for m in m1:
    ret = (ret + m1[m] * m) % MOD
print ret

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N, X = map(int, input().split())
S = list(map(int, input().split()))

l = list(itertools.permutations(S))

ans = 0
for i in range(len(l)):
    x = X
    for j in range(len(S)):
        x %= l[i][j]
    ans += x % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
N,X=map(int,input().split())
s=list(map(int,input().split()))
import itertools
S_=list(itertools.permutations(s))
ans=[]
for i in S_:
    x_=X
    for j in i:
        x_=x_%j
    ans.append(x_)
print(sum(ans)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, x = map(int, input().split())
s = list(map(int, input().split()))
count = 0
cand = list(itertools.permutations(s))
for i in range(len(cand)):
    remain = x
    for j in range(len(cand[0])):
        remain = remain % cand[i][j]
    count += remain
print(count % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import itertools
mod = 1000000007
total = 0
N, X = map(int, input().split())
S = list(map(int,input().split()))
for v in itertools.permutations(S):
    a = X
    for n in v:
        a = a % n
    total += a
    total %= mod
print(total)

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
res = 0
mod = 10** 9 + 7
S = list(map(int,input().split()))
S.sort()
dp = [[0 for i in range(10**5+1)] for j in range(201)]
#dp[X][I] = Sの前X個だけの集合(無視あり)に対してIstartで得られる集合の個数
dp[0][X] = X
for i in range(10**5+1):
    dp[1][i] = i%S[0]
for i in range(2,N+1):
    for j in range(10**5+1):
        dp[i][j] = (dp[i-1][j%S[i-1]] + (i-1)* dp[i-1][j] ) %mod

ans = dp[N][X]
print(ans)

Submission status: Accepted

Solution code:
def examA():
    ABC =LI(); ABC.sort()
    if ABC[0]==ABC[-1]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    S = SI()
    red = S.count("R")
    if red>N//2:
        print("Yes")
    else:
        print("No")
    return

def examC():
    N,Q = LI()
    S = SI()
    T = [LSI()for _ in range(Q)]
    l = -1; r = N
    while(r-l>1):
        cur = (r+l)//2
        now = copy.deepcopy(cur)
        flag = False
        for t,d in T:
            if S[now]==t:
                if d=="R":
                    now += 1
                else:
                    now -= 1
            if now==N:
                flag = True
                break
            if now==-1:
                break
        if flag:
            r = cur
        else:
            l = cur
    R = r
    l = -1; r = N
    while(r-l>1):
        cur = (r+l)//2
        now = copy.deepcopy(cur)
        flag = False
        for t,d in T:
            if S[now]==t:
                if d=="R":
                    now += 1
                else:
                    now -= 1
            if now==-1:
                flag = True
                break
            if now==N:
                break
        if flag:
            l = cur
        else:
            r = cur
    L = l
    ans = max(0,R-L-1)
    print(ans)
    return

def examD():
    N, X = LI()
    S = LI()
    S.sort(reverse=True)
    dp = [[0]*(X+1)for _ in range(N+1)]
    dp[0][X] = 1
    for i in range(N):
        s = S[i]
        for j in range(X+1):
            dp[i+1][j%s] += dp[i][j]
            dp[i+1][j%s] %= mod
        for j in range(X+1):
            dp[i+1][j] += dp[i][j]*(N-i-1)
            dp[i+1][j] %= mod
    #print(dp)
    ans = 0
    for i,d in enumerate(dp[-1]):
        ans += d*i
        ans %= mod
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
s = list(map(int,input().split()))
mod = 10**9 + 7

s.sort(reverse=True)
dp = [[0] * (10**5+1) for _ in range(n+1)]

dp[0][x] = 1
for i in range(n):
    for j in range(10**5+1):
        dp[i+1][j] += dp[i][j] * (n-1-i)
        dp[i+1][j%s[i]] += dp[i][j]
        dp[i+1][j] %= mod
        dp[i+1][j%s[i]] %= mod

ans = 0
for i in range(10**5+1):
    ans += i*dp[-1][i]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, X = map(int, input().split())
S = list(map(int, input().split()))
mod = 10**9 + 7
S.sort(reverse=True)
dp = [0] * (X+1)
dp[X] = 1
for i in range(N):
    ndp = dp[:]
    for j in range(X+1):
        # not use
        ndp[j] = ndp[j] * (N - i - 1) % mod
        # use
        ndp[j % S[i]] = (ndp[j % S[i]] + dp[j]) % mod
    dp = ndp
ans = 0
for j in range(X+1):
    ans = (ans + dp[j] * j) % mod
print(ans)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
S=list(map(int,input().split()))
S.sort(reverse=True)
DP=[[0]*(X+1) for i in range(N+1)]
mod=10**9+7
inv=[0,1]
for i in range(2,N+10):
  inv.append((-inv[mod%i]*(mod//i))%mod)
DP[0][X]=1
for i in range(N):
  DP[0][X]=DP[0][X]*(i+1)%mod
for i in range(N):
  for j in range(X+1):
    DP[i+1][j]=(DP[i+1][j]+DP[i][j]*(1-inv[N-i]))%mod
    DP[i+1][j%S[i]]=(DP[i+1][j%S[i]]+DP[i][j]*inv[N-i])%mod
P=0
for i in range(X+1):
  P=(P+DP[N][i]*i)%mod
print(P)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9+7

def main():
    N, X = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    L = max(A[-1], X)

    dp = [[0]*N for _ in range(L+1)]
    a = A[0]
    for x in range(L+1):
        dp[x][0] = x%a

    dp1 = [0 for _ in range(L+1)] #累積和見たいな
    for n in range(1, N):
        a = A[n]
        for x in range(L+1):
            dp1[x] = ((n-1) * dp1[x] + dp[x][n-1]) % mod
            dp[x][n] = dp1[x%a]

    ans = 0
    t = 1
    for n in reversed(range(N)):
        ans = (ans + dp[X][n]*t) % mod
        t = t * n % mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7
n, X = map(int, input().split())
s = [int(x) for x in input().split()]
s = sorted(s, reverse=True)

dp = [[0 for _ in range(X+1)] for _ in range(n)]
dp[-1][X] = 1

for i in range(n):
    for x in range(X+1):
        dp[i][x % s[i]] += dp[i-1][x]
        dp[i][x % s[i]] %= mod
        dp[i][x] += dp[i-1][x]*(n-i-1)
        dp[i][x] %= mod

dp[-1][X] -= 1
ans = 0

for x in range(X+1):
    ans += dp[n-1][x]*x
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
n, X = map(int, input().split())
s = [int(x) for x in input().split()]
s = sorted(s)

dp = [[0 for _ in range(X+1)] for _ in range(n+1)]

for i in range(n+1):
    if i == 0:
        for x in range(X+1):
            dp[i][x] = x
    else:
        for x in range(X+1):
            dp[i][x] = dp[i-1][x % s[i-1]] + dp[i-1][x]*(i-1)
            dp[i][x] %= mod

ans = dp[n][X]

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
n, X = map(int, input().split())
s = [int(x) for x in input().split()]
s = sorted(s)

dp = [[0 for _ in range(X+1)] for _ in range(n+1)]
inv = [pow(i, mod-2, mod) for i in range(n+1)]

for i in range(n+1):
    if i == 0:
        for x in range(X+1):
            dp[i][x] = x
    else:
        for x in range(X+1):
            dp[i][x] = dp[i-1][x % s[i-1]] * inv[i] + dp[i-1][x]*(1-inv[i])
            dp[i][x] %= mod

ans = dp[n][X]

for i in range(n):
    ans *= i+1
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
mod = 10 ** 9 + 7

N, X = map(int, input().split())
S = list(map(int, input().split()))
S.sort()

dp = defaultdict(int)
dp[X] = 1

for i in reversed(range(N)):
    a = S[i]
    newDP = defaultdict(int)
    for key, val in dp.items():
        newDP[key] += val * i
        newDP[key] %= mod
        newDP[key % a] += val
        newDP[key % a] %= mod
    dp = newDP

ans = 0
for k, v in dp.items():
    ans = (ans + k * v) % mod
print(ans)