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 = 1000000007
numbers = S[:]
numbers.sort()
#dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
#dp = [[0] * (X+1) for _ in range(N+1)]

#dp[0] = [x for x in range(X+1)]
from collections import defaultdict
dp = defaultdict(lambda: defaultdict(int))
for x in range(X+1):
    dp[0][x] = x


for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        #dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i #% MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)

Submission status: Time Limit Exceeded

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

MOD = 1000000007
numbers = S[:]
numbers.sort()
#dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
dp = [[0] * (X+1) for _ in range(N+1)]

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

for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        #dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i #% MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)

Submission status: Time Limit Exceeded

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

MOD = 1000000007
numbers = S[:]
numbers.sort()
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]

#for x in range(X+1):
#    dp[0][x] = x
dp[0] = [x for x in range(X+1)]

for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        #dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i #% MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)

Submission status: Time Limit Exceeded

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



MOD = 1000000007
numbers = S[:]
numbers.sort()
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]

for x in range(X+1):
    dp[0][x] = x

for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        #dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i #% MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)

Submission status: Time Limit Exceeded

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

#import time
#start = time.time()

MOD = 1000000007
numbers = S[:]
numbers.sort()
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]

for x in range(X+1):
    dp[0][x] = x

for i in range(N):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % numbers[i]]
        #dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i #% MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)
#elapsed_time = time.time() - start
#print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Time Limit Exceeded

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

MOD = 1000000007
numbers = S[:]
numbers.sort()
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]

for x in range(X+1):
    dp[0][x] = x

for i in range(N):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % numbers[i]]
        dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i % MOD
        dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X])

Submission status: Time Limit Exceeded

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

numbers = S[:]

import math

def dps(numbers, x):
    min_n = min(numbers)
    if x < min_n:
        return x * math.factorial(len(numbers))
    
    if len(numbers) == 1:
        return x % numbers[0]
    
    ret = 0
    for i, n in enumerate(numbers):
        x_mod = x % n
        if x_mod == 0:
            ret += x_mod
        ret += dps(numbers[0:i] + numbers[i+1:], x_mod)
    return ret
        
ans = dps(numbers, X)
ans = ans % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

numbers = S[:]

def dps(numbers, x):
    if len(numbers) == 1:
        return x % numbers[0]
    
    ret = 0
    for i, n in enumerate(numbers):
        x_mod = x % n
        if x_mod == 0:
            ret += x_mod
        ret += dps(numbers[0:i] + numbers[i+1:], x_mod)
    return ret
        
ans = dps(numbers, X)
ans = ans % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

numbers = S[:]

def dps(numbers, x):
    if len(numbers) == 1:
        return x % numbers[0]
    
    ret = 0
    for i, n in enumerate(numbers):
        ret += dps(numbers[0:i] + numbers[i+1:], x % n)
    return ret
        
ans = dps(numbers, X)
ans = ans % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
input = raw_input

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

c = 0
def perm(lst,x):
    if len(lst) == 0:
        return x
    elif len(lst) == 1:
        return x % lst[0]
    else:
        cc = 0
        for i in range(len(lst)):
            lst2 = lst[:]
            lst2.pop(i)
            if x % lst[i] < min(lst2):
                cc += (x % lst[i]) * math.factorial(len(lst2))
            else:
                cc += perm(lst2, x % lst[i])
        return cc

print(perm(s,X) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def cul(i,x):
    if tmp[i][x]==-1:
        tmp[i][x]=( cul(i+1,x)*(N-1-i) + cul(i+1,x%a[i]) )%MOD
    return tmp[i][x]

MOD=10**9+7
N,x=map(int,input().split())

a=list(map(int,input().split()))
a.sort(reverse=True)
tmp= [[-1 for j in range(x+1)] for i in range(N)] + [[j for j in range(x+1)]]
for i in range(N-1,-1,-1):
    for j in range(x+1):
        tmp[i][j]=( tmp[i+1][j]*(N-1-i) + tmp[i+1][j%a[i]] )  % MOD

print(tmp[0][x])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,x=map(int,input().split())
s=[i for i in input().split()]
mod=10**9+7
ans=0
X=str(x)
for i in itertools.permutations(s, n):
    i=list(i)
    A=eval('%'.join([X]+i))
    ans+=A
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
n,x=map(int, input().split())
s=list(map(int, input().split()))
ans=0
for v in itertools.permutations(s, n):
    xx=x
    for i in range(n):
        xx=xx%v[i]
    ans+=xx
print(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()))
ans = 0

for tpl in itertools.permutations(S):
    x = X
    if 1 in tpl:
        continue

    for y in tpl:
        x = x % y
        if x == 0 or x == 1:
            break
    ans += x
print(ans % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools

MOD = 1000000007  # type: int


memory = {}


def fact(n):
    if n <= 1:
        return 1
    elif n in memory:
        return memory[n]
    else:
        memory[n] = (fact(n-1)*n) % MOD
        return memory[n]


ffmemory = {}


def fact_fromto(n, m):
    if m < 1:
        m = 1
    if n <= 1:
        return 1
    if n == m:
        return 1
    elif (n, m) in ffmemory:
        return ffmemory[(n, m)]
    else:
        ffmemory[(n, m)] = n * fact_fromto(n-1, m) % MOD
        return ffmemory[(n, m)]


def dfs(N, X, S):
    # print(N, X, S)
    if N == 0:
        return X

    ans = 0
    for i, s in enumerate(S):
        ans += dfs(i, X % s, S[:i])*fact_fromto(N-1, i)
        # print("ans", ans)

    return ans % MOD


def solve(N: int, X: int, S: "List[int]"):
    print(dfs(N, X, sorted(S)))

    # ans = 0
    # for x in itertools.permutations(S):
    #     curr = X
    #     for i in x:
    #         curr = curr % i
    #     ans = (ans + curr) % MOD
    # print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    S = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, X, S)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
MOD = 10**9 + 7
dp = [[i % S[0] for i in range(X + 1)] for _ in range(N)]
for i in range(1, N):
  for j in range(X + 1):
    dp[i][j] = dp[i - 1][j % S[i]] + dp[i - 1][j] * i
    dp[i][j] %= MOD
print(dp[N - 1][X])

Submission status: Time Limit Exceeded

Solution code:
N, X = [int(i) for i in input().split()]
sList = [int(i) for i in input().split()]
sList.sort(reverse=True)
mod = 10 ** 9 + 7

dp = [0 for _ in range(X + 1)]
dp[X] = 1
for i, s in enumerate(sList):
    new_dp = [0 for _ in range(X + 1)]
    for x in range(X + 1):
        new_dp[x] += dp[x] * (N - i - 1)
        new_dp[x] %= mod
        new_dp[x % s] += dp[x]
        new_dp[x % s] %= mod
    dp = new_dp

ans = 0
for i in range(len(dp)):
    ans += i * dp[i]
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import math
import itertools

A = list(map(int, input().split(" ")))
X = int(A[1])
Y = int(A[0])

B = list(map(int, input().split(" ")))
ans = 0
p = list(itertools.permutations(B, Y))
Z = math.factorial(Y)
minB = min(B)
for i in range(Z):
    tempX = X
    for k in range(Y):
        tempX = tempX % p[i][k]
        if tempX < minB:
            break
    ans = ans + tempX

ans = ans % 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
MOD = int(1e9 + 7)
memo = [{} for _ in range(N + 1)]
fact = [1]
for i in range(1, 209):
    fact.append(fact[-1] * i % MOD)
#print(fact)
def solve(n, x):
    if n == 0:
        return x % MOD
    if x in memo[n]:
        return memo[n][x]
    memo[n][x] = 0
    if x < S[0]:
        memo[n][x] += fact[n] * x
        memo[n][x] %= MOD
        return memo[n][x]
    for i in range(n):
        memo[n][x] += solve(n - 1, x % S[i])
        memo[n][x] %= MOD
    return memo[n][x]
print(solve(N, X))

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
MOD = int(1e9 + 7)
memo = [{} for _ in range(N + 1)]
def solve(n, x):
    if n == 0:
        return x % MOD
    if x in memo[n]:
        return memo[n][x]
    memo[n][x] = 0
    for i in range(n):
        memo[n][x] += solve(n - 1, x % S[i])
        memo[n][x] %= MOD
    return memo[n][x]
print(solve(N, X))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = defaultdict(int)
dp[x] = 1
for i in range(n):
	dpp = defaultdict(int)
	for j in range(x+1):
		dpp[j] += (n-1-i) * dp[j]
		dpp[j%s[i]] += dp[j]
	for j in range(x+1):
		dpp[j] %= MOD
	dp = dpp
#print(dp)
ans = 0
for j in range(x+1):
	ans += dp[j] * j
	ans %= MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = [[0 for _ in range(x+1)] for _ in range(n+1)]
dp[0][x] = 1
for i in range(n):
	for j in range(x+1):
		dp[i+1][j] += (n-1-i) * dp[i][j]
		dp[i+1][j%s[i]] += dp[i][j]
	for j in range(x+1):
		dp[i+1][j] %= MOD
#print(dp)
ans = 0
for j in range(x+1):
	ans += dp[n][j] * j
	ans %= MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = [[0 for _ in range(x+1)] for _ in range(n+1)]
dp[0][x] = 1
for i in range(n):
	for j in range(x+1):
		dp[i+1][j] += (n-1-i) * dp[i][j]
		dp[i+1][j%s[i]] += dp[i][j]
	for j in range(x+1):
		dp[i+1][j] %= MOD
#print(dp)
ans = 0
for j in range(x+1):
	ans += dp[n][j] * j
	ans %= MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
#input
[N,X] = list(map(int,input().split()))
S = list(map(int,input().split()))
#S.sort()

#[N,X] = [10, 100000]
#S = [50001, 50000, 50002, 50003, 50004, 50005, 50006, 50007, 50008, 50009]


#DP(i,x) i回目で現在x

#initial

DP = np.array([[float(0)]*(X+1)]*(N+1))
DP[N] = [i for i in range(X+1)]
for i in range(N-1,-1,-1):
    for x in range(X+1):
        S_temp = [i for i in S if i <= x]
        if len(S_temp) == 0:
            DP[i][x] = DP[i+1][x]
        else:
            for j in range(len(S_temp)):
                DP[i][x] += DP[i+1][x%S_temp[j]]
            DP[i][x] = DP[i][x] / len(S_temp)
ans = DP[0][X]            
for i in range(1,N+1):
    ans = (ans*i)%(10**9+7)

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
#input
[N,X] = list(map(int,input().split()))
S = list(map(int,input().split()))
S.sort()


#DP(i,x) i回目で現在x

#initial

DP = np.array([[float(0)]*(X+1)]*(N+1))
DP[N] = [i for i in range(X+1)]
for i in range(N-1,-1,-1):
    for x in range(X+1):
        S_temp = [i for i in S if i <= x]
        if len(S_temp) == 0:
            DP[i][x] = DP[i+1][x]
        else:
            for j in range(len(S_temp)):
                DP[i][x] += DP[i+1][x%S_temp[j]]
            DP[i][x] = DP[i][x] / len(S_temp)
ans = DP[0][X]            
for i in range(1,N+1):
    ans = (ans*i)%(10**9+7)

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
n, x = [int(i) for i in input().split()]
S = [int(i) for i in input().split()]
DP = [[0] * (x + 1) for i in range(n + 1)]
DP[0][x] = 1
p = 10 ** 9 + 7
S.sort(reverse=True)

for i in range(n):
    for j in range(x + 1):
        if i != n - 1:
            DP[i + 1][j] += DP[i][j] * (n - i - 1)
        DP[i + 1][j % S[i]] += DP[i][j]

print(sum(i * d % p for i, d in enumerate(DP[n])) % p)

Submission status: Time Limit Exceeded

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

s_list.sort(reverse=True)

mod = 10 ** 9 + 7

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

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

ans = 0
for x in range(1, X + 1):
    ans += dp[N][x] * x
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
n, x = map(int, input().split())
s = map(int, input().split())
a = list(itertools.permutations(s, n))
summ = 0
for i in a:
    i2 = list(i)
    x2 = copy.copy(x)
    while i2:
        x2 = x2 % i2.pop()
    summ += x2

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

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
dp[1] = [i % S[0] for i in range(X+1)]
S = [None] + S

for i in range(2, N+1):
    for j in range(X+1):
        dp[i][j] = (dp[i-1][j]*(i-1) + dp[i-1][j%S[i]]) % mod


print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

MOD = 10 ** 9 + 7

S = [0] * (x+1)
T = [0] * (x+1)

S[x] = 1

for i in range(n-1, -1, -1):
    T = [0] * (x + 1)
    for j in range(x+1):
        S[j] %= MOD
        T[j] += S[j] * i % MOD
        T[j % a[i]] += S[j]
    S, T = T, S

print(sum(i * S[i] % MOD for i in range(a[0]) ) % MOD)

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().split())
ss = list(map(int, input().split()))
import itertools
def modulo(x, p):
    for i in p:
        x %= i
    return x
print(sum(modulo(x, p) for p in itertools.permutations(ss)) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

n,m = map(int,input().split())

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

s.sort()

s = [None] + s

dp = [[0 for i in range(m+1)] for j in range(n+1)]
dp[1] = [i % s[1] for i in range(m+1)]

for i in range(2,n+1):
    for j in range(m+1):
        dp[i][j] = (dp[i-1][j] * (i-1) + dp[i-1][j%s[i]]) % mod
print(dp[n][m])

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
S.reverse()
S.insert(0,0) # 1-indexed
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
ans = 0
for x in range(10**5+1):
    ans += (x*dp[N][x])%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
S.reverse()
S.insert(0,0) # 1-indexed
MOD = 10**9+7
dp = [[0]*(10**5+1) for i in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for x in range(10**5+1):
        dp[i+1][x%S[i+1]] += dp[i][x]
        dp[i+1][x] += dp[i][x]*(N-(i+1))
ans = 0
for x in range(10**5+1):
    ans = (ans+(x*dp[N][x]))%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def main():
    N, X = list(map(int, input().split()))
    S = list(map(int, input().split()))
    S = sorted(S, reverse=True)

    dp = [0]*(X+1)
    dp[X] = 1
    for i in range(N):
        new = [0] * (X+1)
        for x in range(X+1):
            xx = x % S[i]
            new[x] += dp[x] * (N-i-1)
            new[x] %= MOD
            new[xx] += dp[x]
            new[xx] %= MOD
        dp = new

    total = 0
    for x in range(X):
        total += dp[x] * x
        total %= MOD
    print(total)

main()

Submission status: Time Limit Exceeded

Solution code:
N,X,*S=map(int,open(0).read().split())
e=enumerate
d=range(X+1)
for i,s in e(sorted(S)):x=d;d=[t*i+x[j%s]for j,t in e(x)]
print(d[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

def main():
    N, X = list(map(int, input().split()))
    S = list(map(int, input().split()))
    S = sorted(S, reverse=True)

    def solve(start, num, x):
        if start == N-1:
            return (num * (x % S[-1])) % MOD
        total = 0
        for i in range(start, N-1):
            total = (total + solve(i+1, num, (x % S[i]))) % MOD
            num = (num * (N-i-1)) % MOD
        total = (total + num * (x % S[N-1])) % MOD
        return total
    total = 0
    num = 1
    for i in range(N-1):
        total += solve(i+1, num, (X % S[i]) % MOD)
        num *= N-i-1
    total = (total + num * (X % S[-1])) % MOD
    print(total)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from math import factorial
from collections import Counter

def main():
    N, X = LI()
    S = LI()
    S.sort(reverse=True)
    dp = Counter()
    dp[X] = factorial(N)
    for i, s in enumerate(S):
        pre = dp
        dp = Counter()
        for n, cnt in pre.items():
            dp[n] += cnt * (N - 1 - i) // (N - i)
            dp[n % s] += cnt // (N - i)
    ans = 0
    for n, cnt in dp.items():
        ans = (ans + (n * cnt) % MOD) % MOD

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from math import factorial
from bisect import bisect
from functools import reduce

def func(x, arr):
    p = bisect(arr, x)
    num = 1
    for i in range(p + 1, len(arr) + 1):
        num = (num * i) % MOD
    arr = arr[:p]
    if len(arr) == 0:
        return x * num
    ret = 0
    num2 = 1
    for i in range(len(arr) - 1, -1, -1):
        tmp = func(x % arr[i], arr[:i]) * num2 % MOD
        ret = (ret + tmp) % MOD
        num2 = num2 * i % MOD
    return ret * num % MOD

def main():
    N, X = LI()
    S = LI()
    S.sort()
    ans = func(X, S)

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from math import factorial
from bisect import bisect
from functools import reduce

def func(x, arr):
    p = bisect(arr, x)
    num = 1
    for i in range(p + 1, len(arr) + 1):
        num = (num * i) % MOD
    arr = arr[:p]
    if len(arr) == 0:
        return x * num
    ret = 0
    for i in range(len(arr)):
        ret = (ret + func(x % arr[i], arr[:i] + arr[i + 1:])) % MOD
    return ret * num % MOD

def main():
    N, X = LI()
    S = LI()
    S.sort()
    ans = func(X, S)

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 II(): return int(sys.stdin.readline())
def SI(): return input()
from math import factorial

def func(x, arr):
    if len(arr) == 0:
        return x
    if x < arr[0]:
        return x * factorial(len(arr)) % MOD
    ret = 0
    for i in range(len(arr)):
        ret = (ret + func(x % arr[i], arr[:i] + arr[i + 1:])) % MOD
    return ret

def main():
    N, X = LI()
    S = LI()
    S.sort()
    ans = func(X, S)

    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD=10**9+7
N,x=map(int,input().split())
 
a=list(map(int,input().split()))
a.sort()
a.reverse()
table=np.arange(x+1)


for i in range(N-1,-1,-1):
	tmp=table.copy()
	for j in range(x+1):
		table[j]=( tmp[j]*(N-1-i) + tmp[j%a[i]] ) % MOD
 
print(int(table[x]))

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = sorted([int(a) for a in input().split()])[::-1]
P = 10**9+7
fact = [1]
for i in range(N+10):
    fact.append(fact[-1]*(i+1)%P)

def calc(k, x):
    if k >= N:
        return x
    if x == S[-1]:
        return 0
    if x < S[-1]:
        return (x*fact[N-k]) % P
    return (calc(k+1, x%S[k]) + calc(k+1, x) * (N-k-1)) % P

print(calc(0, X))

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = sorted([int(a) for a in input().split()])[::-1]
P = 10**9+7
fact = [1]
for i in range(N+10):
    fact.append(fact[-1]*(i+1)%P)

def calc(k, x):
    if k >= N:
        return x
    if x < S[-1]:
        return (x*fact[N-k]) % P
    return (calc(k+1, x%S[k]) + calc(k+1, x) * (N-k-1)) % P

print(calc(0, X))

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
N,x=map(int,input().split())
 
a=list(map(int,input().split()))
a.sort()
a.reverse()
table=[[0 for i in range(N+1)] for j in range(x+1)]
for i in range(x+1):
	table[i][N]=i
 
for i in range(N-1,-1,-1):
	for j in range(x+1):
		table[j][i]=(table[j][i+1]*(N-1-i)+table[j%a[i]][i+1]) % MOD
 
print(table[x][0])

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
N,x=map(int,input().split())

a=list(map(int,input().split()))
a.sort()
a.reverse()
table=[[0 for i in range(N+1)] for j in range(x+1)]
for i in range(x+1):
	table[i][N]=i

for i in range(N-1,-1,-1):
	for x in range(x+1):
		table[x][i]=(table[x][i+1]*(N-1-i)+table[x%a[i]][i+1]) % MOD 

print(table[x][0])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def div(a, b):
    return a * power(b, MOD-2) % MOD


fact = [1] * 201
for i in range(1, 201):
    fact[i] = (i * fact[i-1]) % MOD

inv = [1] * 201
for i in range(1, 201):
    inv[i] = div(1, i)


def main():
    N, X = map(int, input().split())
    S = list(map(int, input().split()))
    S.sort(reverse=True)
    dp = [[0] * (X+1) for _ in range(N)]
    for x in range(X+1):
        dp[N-1][x] = x % S[N-1]
    for i in range(N-2, -1, -1):
        for x in range(X+1):
            p1 = dp[i+1][x % S[i]]
            p2 = dp[i+1][x]
            dp[i][x] = ((p1 + p2 * (N-i-1)) * inv[N-i]) % MOD
    print((dp[0][X] * fact[N]) % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
N,X=map(int,input().split())
S=[int(i) for i in input().split()]
S.sort(reverse=True)

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return ((power(x,y//2)**2)*x)%mod
inv=[0]*(N+1)
for i in range(N+1):
  inv[i]=power(i,mod-2)
dp=[[0]*(X+1) for i in range(N+1)]
for x in range(X+1):
  dp[N][x]=x
for i in range(N)[::-1]:
  for x in range(X+1):
    dp[i][x]+=dp[i+1][x%S[i]]*inv[N-i]
    dp[i][x]%=mod
    dp[i][x]+=(N-i-1)*dp[i+1][x]*inv[N-i]
    dp[i][x]%=mod
print((dp[0][X]*Factorial[N])%mod)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
N,X=map(int,input().split())
S=[int(i) for i in input().split()]
S.sort(reverse=True)

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod
inv=[0]*(N+1)
for i in range(N+1):
  inv[i]=power(i,mod-2)
dp=[[0]*(X+1) for i in range(N+1)]
for x in range(X+1):
  dp[N][x]=x
for i in range(N)[::-1]:
  for x in range(X+1):
    dp[i][x]=dp[i+1][x%S[i]]*inv[N-i]+(N-i-1)*dp[i+1][x]*inv[N-i]
    dp[i][x]%=mod
print((dp[0][X]*Factorial[N])%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import bisect
N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
mod = 10**9+7

fact_memo = [0]*201
fact_memo[0] = 1
def fact(n):
    if fact_memo[n] == 0:
        fact_memo[n] = n*fact(n-1)%mod
    return fact_memo[n]

fact_inv_memo = [0]*201
fact_inv_memo[0] = 1
def fact_inv(n):
    if fact_inv_memo[n] == 0:
        fact_inv_memo[n] = pow(fact(n),mod-2,mod)
    return fact_inv_memo[n]

dp = defaultdict(lambda :-1)
import sys
sys.setrecursionlimit(100000000)
def rec(n,x):
    if dp[(n,x)] != -1:
        return dp[(n,x)]
    if n == 0:
        dp[(n,x)] = x%S[0]
        return dp[(n,x)]
    s = S[:n+1]
    if x <= s[-1]:
        k = bisect.bisect(s,x)
        if k == 0:
            dp[(n,x)] = x*fact(n+1)%mod
        else:
            dp[(n,x)] = fact(n+1)*fact_inv(k)*rec(k-1,x)%mod
    else:
        res = rec(n-1,x%s[-1])+n*rec(n-1,x)
        dp[(n,x)] = res%mod
    return dp[(n,x)]

print(rec(N-1,X))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, X = map(int, input().split())
S = [int(s) for s in input().split()]
S.sort(reverse=True)
NN = 10 ** 9 + 7

dp = {}

def f(i, x):
    if i == N:
        return x
    if (i, x) in dp.keys():
        return dp[(i, x)]

    result = (f(i + 1, x % S[i]) + f(i + 1, x) * (N - i - 1))
    dp[(i, x)] = result
    return result

print(int(f(0, X) % NN))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import bisect
N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
mod = 10**9+7

fact_memo = [0]*201
fact_memo[0] = 1
def fact(n):
    if fact_memo[n] == 0:
        fact_memo[n] = n*fact(n-1)%mod
    return fact_memo[n]

fact_inv_memo = [0]*201
fact_inv_memo[0] = 1
def fact_inv(n):
    if fact_inv_memo[n] == 0:
        fact_inv_memo[n] = pow(fact(n),mod-2,mod)
    return fact_inv_memo[n]

dp = defaultdict(lambda :-1)
import sys
sys.setrecursionlimit(100000000)
def rec(n,x):
    if dp[(n,x)] != -1:
        return dp[(n,x)]
    if n == 0:
        dp[(n,x)] = x%S[0]
        return dp[(n,x)]
    s = S[:n+1]
    if x <= s[-1]:
        k = bisect.bisect(s,x)
        if k == 0:
            dp[(n,x)] = x*fact(n+1)%mod
        else:
            dp[(n,x)] = fact(n+1)*fact_inv(k)*rec(k-1,x)%mod
    else:
        res = x%s[0]*fact(n)%mod
        for i in range(1,n+1):
            res += fact(n)*fact_inv(i)*rec(i-1,x%s[i])%mod
        dp[(n,x)] = res%mod
    return dp[(n,x)]

print(rec(N-1,X))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, X = map(int, input().split())
S = [int(s) for s in input().split()]
S.sort(reverse=True)
NN = 10 ** 9 + 7

fact = [1]
for i in range(1, N+1):
    fact.append((fact[i-1] * i) % NN)

dp = {}

def f(i, x):
    if i == N:
        return x
    if (i, x) in dp.keys():
        return dp[(i, x)]

    result = (f(i + 1, x % S[i]) + f(i + 1, x) * (N - i - 1))
    dp[(i, x)] = result
    return result

print(int(f(0, X) % NN))

Submission status: Time Limit Exceeded

Solution code:
N,X=map(int, input().split())
S=[int(c) for c in input().split()]
S.sort()
dp=dict()
def find(x, n):
    if (x, n) in dp:
        return dp[(x, n)]
    if n == 0:
        return x % S[n]
    dp[(x, n)] = ((n+1)*find(x, n-1)) if x < S[n] else (n*find(x, n-1) + find(x%S[n], n-1))
    return dp[(x, n)]
print(find(X, N-1)%(10**9+7))