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=[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*find(x, n-1) + find(x%S[n], n-1)
    return dp[(x, n)]
print(find(X, N-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n,x =  list(map(int,input().split()))
s = list(map(int,input().split()))
s.sort(reverse=True)
dp = [[0 for j in range(x+1)] for i in range(n+1)]
dp[0][x]=1
inf = 10**9+7
for i in range(n):
    for j in range(1,x+1):
        dp[i+1][j]=dp[i+1][j]+dp[i][j]*(n-i-1)
        dp[i+1][j%s[i]]=dp[i+1][j%s[i]]+dp[i][j]

answer=0
for j in range(1,x+1):
    answer+=dp[n][j]*j
    answer%=inf
    
print(answer)

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)]
    dp[(x, n)] = (x % S[n]) if n == 0 else (n*find(x, n-1) + find(x%S[n], n-1))
    return dp[(x, n)]
print(find(X, N-1)%(10**9+7))

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)]
    dp[(x, n)] = (x % S[n]) if n == 0 else (n*find(x, n-1) + find(x%S[n], n-1))
    return dp[(x, n)]
print(find(X, N-1)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,X = map(int, input().split())
s_list = list(map(int, input().split())) # "1 2 3"と入力
keep_list = []
main_dic={}

for i in range(N):
    keep_list.append([])
    main_dic.setdefault(i,[])
    middle_dic={}
    for moji in s_list:
        if i==0:
            left=X%moji
            middle_dic[str(moji)]=X%moji
        else:
            key_list=main_dic[i-1][0].keys()
            for key_moji in key_list:
                key_moji_list=key_moji.split(',')
                if (str(moji) in key_moji_list)==False:
                    now_moji=key_moji+','+str(moji)
                    middle_dic[str(now_moji)]=main_dic[i-1][0][key_moji]%moji
        #print(middle_dic)
    main_dic.setdefault(i,[]) 
    main_dic[i].append(middle_dic)
#print(main_dic)
print(sum(main_dic[N-1][0].values())%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

N,X = map(int,raw_input().split())
S = map(int,raw_input().split())
MOD = 10**9 + 7

S.sort()

dp = [[0 for i in range(X+1)] for j in range(N+1)]

for i in range(X+1):
  dp[1][i] = i % S[0]

for n in range(2,N+1):
  for x in range(X+1):
    #print n,x
    dp[n][x] =  dp[n-1][x] * (n-1) 
    dp[n][x] += dp[n-1][x%S[n-1]]
    dp[n][x] %= MOD

print dp[N][X]

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

S = [int(x) for x in input().split()]

iterlist = list(itertools.permutations(S))
total = []
for i in iterlist:
    x = X
    i= list(i)
    for j in range(N):

        y = i.pop(0)
        x = x % y
        if x == 0:
            break
    total.append(x)

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

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
SS = input()
S = SS.split(" ")
count = 0

for i in range(N):
    S[i] = int(S[i])

S.sort()
Smin = S[0]

def copy(s):
    ss = []
    for i in s:
        ss.append(i)
    
    return ss

def a(S, n, X):
    global count
    if X == 0:
        return
    if X < Smin:
        c = 1
        for i in range(1, len(S) + 1):
            c *= i
        count += X * c
        return
    for i in range(n):
        s = copy(S)
        b = s.pop(i)
        if len(s) == 0:
            count += X % b
        else:
            a(s, n - 1, X % b)

a(S, N, X)

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

n,x = map(int,raw_input().split())
s = map(int,raw_input().split())

s.sort(reverse=True)
ans = 0

def dfs(xx,ss):
  ans = 0
  if len(ss)==1:
    return xx % ss[0]

  for q in ss:
    x2 = xx % q
    s2 = copy.deepcopy(ss)
    s2.remove(q)
    if x2 < min(s2):
      ans += math.factorial( len(s2) ) * x2
    else:
       ans += dfs(x2,s2)
  return ans

print dfs(x,s) % (10**9 + 7)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b,c = LI()
    if a == b and b == c:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = I()
    s = S()
    r = s.count("R")
    if r > n//2:
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    n,q = LI()
    s = S()

    return

#D
fact = [1 for i in range(200+1)]
for i in range(200):
    fact[i+1] = fact[i]*(i+1)%mod
ans = 0
def dfs(d,x,k,m,n):
    global ans
    if x < m:
        ans += x*fact[n-d]%mod
        ans %= mod
    else:
        for i in range(len(k)):
            dfs(d+1,x%k[i],k[:i]+k[i+1:],m,n)
def D():
    n,x = LI()
    s = LI()
    m = min(s)
    k = [s[i] for i in range(n)]
    dfs(0,x,k,m,n)
    print(ans%mod)
    return

#E
def E():
    def com(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod
    fact = [1 for i in range(100001)]
    for i in range(100000):
        fact[i+1] = fact[i]*(i+1)%mod
    inv = [1 for i in range(100001)]
    inv[100000] = pow(fact[100000],mod-2,mod)
    for i in range(100000)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    b,w = LI()
    n = b+w
    po = [1 for i in range(100001)]
    for i in range(100000):
        po[i+1] = po[i]*2%mod
    inp = [1 for i in range(100001)]
    inp[100000] = pow(po[100000],mod-2,mod)
    for i in range(100000)[::-1]:
        inp[i] = inp[i+1]*2%mod
    for i in range(1,n+1):
        ans = 0
        if i < n:
            if i < b:
                for k in range(1,i+1):
                    ans += inp[i]*com(i-1,k-1)%mod
                    ans %= mod
            else:
                for k in range(1,b):
                    ans += inp[i]*com(i-1,k-1)%mod
                    ans %= mod
                for k in range(b,i+1):
                    ans += inp[i-1]*com(i-1,k-1)%mod
                    ans %= mod
        else:
            for k in range(n-w+1,b):
                ans += inp[i]*com(i-1,k-1)%mod
                ans %= mod
            for k in range(b,i):
                ans += inp[i-1]*com(i-1,k-1)%mod
                ans %= mod
            ans *= inp[i-2]*com(i-1,k-1)%mod
            ans %= mod
        print(ans)
        print
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

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

seq = [i for i in range(N)]
pat = itertools.permutations(seq)
min_S = min(S)
memo = dict()

## dfsで枝刈りありで解いていく
param = [i for i in range(N)] # N番目が存在するか
nums = str(X)

def dfs(x, param, nums):
    #print("dfs", x, param, nums)
    l = len(param)
    if l == 0:
        #print("-", x)
        return x

    if x == 0:
        #print("return0", x)
        return 0

    if x < min_S: 
        #print("min", x)
        x *= math.factorial(l)
        #print("return1", x)
        return x
    
    summ = 0
    for i in param:
        p2 = copy.deepcopy(param)
        p2.remove(i)
        #print(i, p2)
        summ += dfs(x % S[i], p2, nums + "," + str(S[i]))
        summ = summ % (10 ** 9 + 7)
    #print("return2", summ)
    return summ

print(dfs(X, param, nums))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce
from functools import lru_cache
input = sys.stdin.readline

# N個整数
n, x = list(map(int, input().split()))

# 1整数
# n = int(input())

# 空白区切りリスト整数
s = list(map(int, input().split()))
##とりあえずソート
s.sort(reverse=True)

zz = 1000000007


# N!を求める
@lru_cache(maxsize=1000)
def dn(n):
    if n >= 1:
        return 1
    return (n * dn(n - 1))%zz


# 黒板にkokubanが書かれているときに i番目以降を適用した場合の答え
@lru_cache(maxsize=2100000)
def amari(i, kokuban):
    if i == n:
        return kokuban
    #if kokuban == 1:
    #    return dn(n-i)
    ret = 0

    ret += amari(i + 1, kokuban % s[i])
    bairitu = 1
    for di in range(1, n - i):
        bairitu *= n - i - di
        ret += bairitu * amari(i + di + 1, kokuban % s[i + di])
    return ret % zz


print(amari(0, x))

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
SS = input()
S = SS.split(" ")
count = 0

for i in range(N):
    S[i] = int(S[i])

S.sort()
Smin = S[0]

def copy(s):
    ss = []
    for i in s:
        ss.append(i)
    
    return ss

def a(S, n, X):
    global count
    if X < Smin:
        c = 1
        for i in range(1, len(S) + 1):
            c *= i
        count += X * c
        return
    for i in range(n):
        s = copy(S)
        b = s.pop(i)
        if len(s) == 0:
            count += X % b
        else:
            a(s, n - 1, X % b)

a(S, N, X)

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

Submission status: Time Limit Exceeded

Solution code:
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int, ss_raw())

INF = 1 << 29
DIV = 10**9 +7
N,X  = ints_raw()
Ss = ints_raw()

Ss.sort()

def rec(n,subSs):
    if len(subSs) ==1:
        return n%subSs[0]
    else:
        neoSub = subSs[:len(subSs)-1]
        return (rec(n,neoSub)*(len(subSs)-1) + rec(n%subSs[-1],neoSub))%DIV

def ans():
    return rec(X,Ss)

print ans()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b,c = LI()
    if a == b and b == c:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = I()
    s = S()
    r = s.count("R")
    if r > n//2:
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    n,q = LI()
    s = S()

    return

#D
def D():
    def dfs(d,x,k,ans):
        if x < m:
            ans += [x*fact[n-d]%mod]
        else:
            for i in range(len(k)):
                dfs(d+1,x%k[i],k[:i]+k[i+1:],ans)
    n,x = LI()
    s = LI()
    m = min(s)
    fact = [1 for i in range(n+1)]
    for i in range(n):
        fact[i+1] = fact[i]*(i+1)%mod
    ans = []
    k = [s[i] for i in range(n)]
    dfs(0,x,k,ans)
    print(sum(ans)%mod)
    return

#E
def E():
    def com(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod
    fact = [1 for i in range(100001)]
    for i in range(100000):
        fact[i+1] = fact[i]*(i+1)%mod
    inv = [1 for i in range(100001)]
    inv[100000] = pow(fact[100000],mod-2,mod)
    for i in range(100000)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    b,w = LI()
    n = b+w
    po = [1 for i in range(100001)]
    for i in range(100000):
        po[i+1] = po[i]*2%mod
    inp = [1 for i in range(100001)]
    inp[100000] = pow(po[100000],mod-2,mod)
    for i in range(100000)[::-1]:
        inp[i] = inp[i+1]*2%mod
    for i in range(1,n+1):
        ans = 0
        if i < n:
            if i < b:
                for k in range(1,i+1):
                    ans += inp[i]*com(i-1,k-1)%mod
                    ans %= mod
            else:
                for k in range(1,b):
                    ans += inp[i]*com(i-1,k-1)%mod
                    ans %= mod
                for k in range(b,i+1):
                    ans += inp[i-1]*com(i-1,k-1)%mod
                    ans %= mod
        else:
            for k in range(n-w+1,b):
                ans += inp[i]*com(i-1,k-1)%mod
                ans %= mod
            for k in range(b,i):
                ans += inp[i-1]*com(i-1,k-1)%mod
                ans %= mod
            ans *= inp[i-2]*com(i-1,k-1)%mod
            ans %= mod
        print(ans)
        print
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
import itertools
def main():
	n, x = map(int, input().split())
	ins = list(map(int, input().split()))
	ps = list(itertools.permutations(ins))
	total = 0
	for ls in ps:
		this_x = x
		for i in range(n):
			this_x %= ls[i]
		total += this_x
		total %= 1000000007

	print(total)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,X=map(int,input().split(' '))
S=sorted(list(map(int,input().split(' '))))[::-1]
results=[X]
results_sub=[]
if N>1:
	for i in range(N-1):
		results_sub = [result%S[i] for result in results]
		for j in range(len(results)):
			results.insert(2*j+1,results_sub[j])

results = [result%S[-1] for result in results]

multimap=[]
if N==1:
	multimap=[1]
else:
	multimap=[1,1]
	if N>2:
		for i in range(N-2):
			multimap = [m*(i+2) for m in multimap] + multimap
ans=0
for i in range(2**(N-1)):
	ans+=(multimap[i] * results[i])
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize=10000)
def fact(n):
    return math.factorial(n) % (10 ** 9 + 7)


N, X = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

tab = [0] * min(S)

S.sort()

@lru_cache(maxsize=10000)
def f(NUM, LIST):
    modL = [NUM % l for l in LIST]
    ret = 0
    fa = fact(len(LIST) - 1)
    for i in range(len(LIST)):
        l = modL[i]

        if l > min(S):
            newL = list(LIST)
            del newL[i]
            ret += f(l, tuple(newL))
        elif l == min(S):
            pass
        else:
            ret += l * fa

    return ret % (10 ** 9 + 7)


print(f(X, tuple(S)) )

Submission status: Time Limit Exceeded

Solution code:
total = 0
def main():
	n, x = map(int, input().split())
	ins = list(map(int, input().split()))
	global total
	def permutations(use_num, step):
		if step == n:
			this_x = x
			for i in range(n):
				this_x %= use_num[i]
			global total
			total += this_x
			total %= 1000000007

		for i in range(step, n):
			use_num_copy = [c for c in use_num]
			use_num_copy[step], use_num_copy[i] = use_num_copy[i], use_num_copy[step]
			permutations(use_num_copy, step + 1)

	permutations(ins, 0)
	print(total)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, X = tuple([int(x) for x in str(input()).split(' ')])
S = [int(x) for x in str(input()).split(' ')]
minS = min(S)
total = 0
for order in itertools.permutations(range(N), N):
    x = X
    for i in order:
        x %= S[i]
        if x < minS:
            break
    total += x

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

Submission status: Time Limit Exceeded

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

answer = 0
mod = 10 ** 9 + 7
memo_dict = {}
fact_dict = {}
for i in range(N):
    if i == 0:
        fact_dict[i] = 1
    else:
        fact_dict[i] = fact_dict[i - 1] * i % mod

# print(fact_dict)


def sumD(x, s, s_list):
    s_list_tmp = s_list[:]
    next_mod = x % s
    s_list_tmp.extend([next_mod, s])
    key = tuple(s_list_tmp)
    if key in memo_dict:
        # print("hit")
        return memo_dict[key]
    min_s = min(s_list)

    if next_mod < min_s:
        value = fact_dict[len(s_list) - 1] * next_mod % mod
        # print("register")
        # print(key, value)
        memo_dict[key] = value
        return value

    if s == min_s:
        value = fact_dict[len(s_list) - 1] * next_mod % mod
        # print("register")
        # print(key, value)
        memo_dict[key] = value
        return value

    s_list2 = s_list[:]
    s_list2.remove(s)
    value = sum([sumD(next_mod, s_i, s_list2) % mod for s_i in s_list2])
    # print("register")
    # print(key, value)
    memo_dict[key] = value
    return value


answer = sum([sumD(X, s, s_list) % mod for s in s_list]) % mod

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math

def permutationListRecursive(data, parent_data, parent_min=None):
    if len(data) == 0:
        return [parent_data]
    if parent_min is not None:
        tmp_data = [d for d in data if d < parent_min]
        if len(tmp_data) == 0:
            return [parent_data]

    a = []
    for d in data:
        data2 = data[:]
        data2.remove(d)
        a += (permutationListRecursive(data2, parent_data + [d], parent_min=d))
    return a

#
# def filter(S):
#     min = S[0]
#     l = 0
#     for i, s in enumerate(S):
#         if s < min:
#             l = i
#             min = s
#     return S[0: l + 1]


# a = [int(each) for each in '5 82'.split()]
a = [int(each) for each in input().split()]
N = a[0]
X = a[1]

# S = list(int(each) for each in '22 11 6 5 13'.split())
S = list(int(each) for each in input().split())
ans = 0

sets = permutationListRecursive(S, [])
# sets = itertools.permutations(S)

test = {}

for s in sets:
    x = X

    m = 0
    for v in s:
        # print('mod by ', v)
        # print(x, '->', x % v)
        x = x % v

    test[x] = test.get(x, 0) + math.factorial(len(S) - len(s))
    ans += x * math.factorial(len(S) - len(s))

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

Submission status: Time Limit Exceeded

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

ans = 0


def solve(layer, now_X, remain):
    global ans

    if len(remain) == 1:
        ans += now_X % remain[0]
    else:
        for i, s in enumerate(remain):
            next_X = now_X % s
            next_remain = remain[:]
            next_remain.pop(i)
            if next_X < min(next_remain):
                ans += math.factorial(len(next_remain)) * next_X
            else:
                solve(layer=layer+1, now_X=next_X, remain=next_remain)

solve(layer=1, now_X=X, remain=S)
print(ans % (pow(10, 9) + 7))

Submission status: Time Limit Exceeded

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

result=[]

def dp(S_, X_):

    if len(S_) == 0:
        result.append(X_)
        return

    for y in S_:
        tmp = [i for i in S_ if i != y]
        dp(tmp, X_%y)

dp(S,X)

print(sum(result)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, X = tuple([int(x) for x in str(input()).split(' ')])
S = [int(x) for x in str(input()).split(' ')]

total = 0
for order in itertools.permutations(range(N), N):
    x = X
    for i in order:
        x %= S[i]
    total += x

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
# import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
N, X = [int(x) for x in stdin.readline().rstrip().split()]
S = [int(x) for x in stdin.readline().rstrip().split()]
S.sort()
MOD = 10**9 +7
ans = 0
memo ={}
def func(S_list,x):
  ans = 0
  if (tuple(S_list),x) in memo:
    return memo[(tuple(S_list),x)]
  if min(S_list)>x:
    return math.factorial(len(S_list))*x
  if len(S_list)==1:
    return x%S_list[0]
  for i,s in enumerate(S_list):
    temp_list = S_list.copy()
    temp_list.remove(s)
    ans += func(temp_list, x%s)
   
  memo[(tuple(S_list),x)] = ans
  return ans
ans = func(S,X)
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize=10000)
def fact(n):
    return math.factorial(n) % (10 ** 9 + 7)


N, X = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

tab = [0] * min(S)

S.sort()

@lru_cache(maxsize=10000)
def f(NUM, LIST):
    modL = [NUM % l for l in LIST]
    ret = 0
    for i in range(len(LIST)):
        l = modL[i]

        if l > min(S):
            newL = list(LIST)
            del newL[i]
            ret += f(l, tuple(newL))
        elif l == min(S):
            pass
        else:
            ret += l * fact(len(LIST) - 1)

    return ret % (10 ** 9 + 7)


print(f(X, tuple(S)) )

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
SS = input()
S = SS.split(" ")
count = 0

for i in range(N):
    S[i] = int(S[i])

def copy(s):
    ss = []
    for i in s:
        ss.append(i)
    
    return ss

def a(S, n, X):
    global count
    for i in range(n):
        s = copy(S)
        b = s.pop(i)
        if len(s) == 0:
            count += X % b
        else:
            a(s, n - 1, X % b)

a(S, N, X)

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

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
import itertools
N,X = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

totallist =  list(itertools.permutations(S))
total = []
for i in totallist:
    x = X
    i= list(i)
    for j in range(N):
        
        y = i.pop(0)
        x = x % y
        if x == 0:
            break
    total.append(x)

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize=10000)
def fact(n):
    return math.factorial(n)


N, X = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

tab = [0] * min(S)

S.sort()

@lru_cache(maxsize=10000)
def f(NUM, LIST):
    modL = [NUM % l for l in LIST]
    ret = 0
    for i in range(len(LIST)):
        l = modL[i]

        if l > min(S):
            newL = list(LIST)
            del newL[i]
            ret += f(l, tuple(newL))

        elif l == min(S):
            pass
        else:
            # ret += l * math.factorial(len(LIST) - 1)
            ret += l * fact(len(LIST) - 1)

    return ret% (10 ** 9 + 7)


print(f(X, tuple(S)) )

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
# import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
N, X = [int(x) for x in stdin.readline().rstrip().split()]
S = [int(x) for x in stdin.readline().rstrip().split()]
# S.sort()
MOD = 10**9 +7
ans = 0
memo ={}
def func(S_list,x):
  ans = 0
  if (tuple(S_list),x) in memo:
    return memo[(tuple(S_list),x)]
  if min(S_list)>x:
    return math.factorial(len(S_list))*x
  if len(S_list)==1:
    return x%S_list[0]
  for i,s in enumerate(S_list):
    temp_list = S_list.copy()
    temp_list.remove(s)
    ans += func(temp_list, x%s)
   
  memo[(tuple(S_list),x)] = ans
  return ans
ans = func(S,X)
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = [int(x) for x in input().split()]
S.sort()
p = 10 ** 9 + 7
P = [1] * N
for i in range(1, N):
  P[i] = P[i - 1] * (i + 1)
  P[i] %= p
C = 0
def xUpdate(X, S, d):
  cnt = 0
  if len(S) == 0:
    return X
  if X < S[0]:
    return X * P[N - 1 - d] % p
  else:
    for i, s in enumerate(S):
      cnt += xUpdate(X % s, S[0:i] + S[i+1:N], d + 1) % p
    return cnt % p
print(xUpdate(X, S, 0))

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
from collections import defaultdict


seq_count, initial_number = map(int, input().split(' '))

sequence = list(map(int, input().split(' ')))

sequence.sort(reverse=True)
# print(sequence)

seq_limited = [item for item in sequence if item < initial_number]
k_count = math.factorial(seq_count) // math.factorial(seq_count - (len(sequence) - len(seq_limited)))
# print(k_count)

calculation_perm_to_count = defaultdict(int)

for perm in itertools.permutations(seq_limited):
    smallest_mod_num = 100001
    calculation_perm_list = []
    for mod_num in perm:
        if mod_num < smallest_mod_num:
            calculation_perm_list.append(mod_num)
            smallest_mod_num = mod_num

    calculation_perm = tuple(calculation_perm_list)
    calculation_perm_to_count[calculation_perm] += k_count

sum_mods = 0

# print(calculation_perm_to_count)

for calc_perm, count in calculation_perm_to_count.items():
    num = initial_number
    for mod_num in calc_perm:
        num = num % mod_num
    sum_mods += num * count

sum_mods = sum_mods % (10**9 + 7)

print(sum_mods)
exit(0)

Submission status: Time Limit Exceeded

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

memo = {}
MOD = 10 ** 9 + 7

def mod(x, ss):
    if (x, tuple(ss)) in memo:
        return memo[(x, tuple(ss))]

    if len(ss) == 1:
        return x % ss[0]

    total = 0
    for s in ss:
        ss2 = ss[:]
        ss2.remove(s)
        total = (total + mod(x % s, ss2)) % MOD

    memo[(x, tuple(ss))] = total
    return total

print(mod(X, Ss))

Submission status: Time Limit Exceeded

Solution code:
import math

[N, X] = list(map(int, input().split()))
s_list = sorted(list(map(int, input().split())))

answer = 0
mod = 10 ** 9 + 7
memo_dict = {}


# x, s_listに対する総和
# x % s, s_list-1 に対する総和の総和


def sumD(x, s, s_list):
    s_list_tmp = s_list[:]
    next_mod = x % s
    s_list_tmp.extend([next_mod, s])
    key = tuple(s_list_tmp)
    if key in memo_dict:
        # print("hit")
        return memo_dict[key]
    min_s = min(s_list)

    if next_mod < min_s:
        value = math.factorial(len(s_list) - 1) * next_mod
        # print("register")
        # print(key, value)
        memo_dict[key] = value
        return value

    if s == min_s:
        value = math.factorial(len(s_list) - 1) * next_mod
        # print("register")
        # print(key, value)
        memo_dict[key] = value
        return value

    s_list2 = s_list[:]
    s_list2.remove(s)
    value = sum([sumD(next_mod, s_i, s_list2) % mod for s_i in s_list2])
    # print("register")
    # print(key, value)
    memo_dict[key] = value
    return value


answer = sum([sumD(X, s, s_list) % mod for s in s_list]) % mod

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize=1000)
def fact(n):
    return math.factorial(n)


N, X = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

tab = [0] * min(S)

S.sort()

def f(NUM, LIST):
    modL = [NUM % l for l in LIST]
    ret = 0
    for i in range(len(LIST)):
        l = modL[i]

        if l > min(S):
            newL = list(LIST)
            del newL[i]
            ret += f(l, newL)

        elif l == min(S):
            pass
        else:
            # ret += l * math.factorial(len(LIST) - 1)
            ret += l * fact(len(LIST) - 1)

    return ret% (10 ** 9 + 7)


print(f(X, S) )

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))
for i in range(math.factorial(Y)):
    tempX = X
    for k in range(Y):
        tempX = tempX % p[i][k]
        if tempX < min(B):
            break
    ans = ans + tempX

ans = ans % 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize=1000)
def fact(n):
    return math.factorial(n)


N, X = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]

tab = [0] * min(S)

S.sort()

def f(NUM, LIST):
    modL = [NUM % l for l in LIST]
    ret = 0
    for i in range(len(LIST)):
        l = modL[i]

        if l > min(S):
            newL = list(LIST)
            del newL[i]
            ret += f(l, newL)

        elif l == min(S):
            pass
        else:
            # ret += l * math.factorial(len(LIST) - 1)
            ret += l * fact(len(LIST) - 1)
    return ret


print(f(X, S) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
import math

n,x = map(int,input().split())
s = [int(a) for a in input().split()]
s.sort()
s = s[::-1]
numbers = np.ones(n) * x
flag = np.zeros(n)

task = [[x,s]]
ans = 0

while(len(task) > 0):
    _x,_s = task.pop()
    _n = len(_s)
    for i in range(_n):
        __x = _x
        __x = __x % _s[i]
        if __x < _s[-1]:
            ans += __x * math.factorial(_n-1)
        else:
            __s = copy.copy(_s)
            __s.remove(_s[i])
            task.append([__x,__s])

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