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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools

n, x = (int(i) for i in input().strip().split(' '))
s = [0]*n
for i, si in enumerate(input().strip().split(' ')):
	s[i] = int(si)


min_s = min(s)

s_list = list(itertools.permutations(s))

list_x = 0

for s_list_i in s_list:
	tmp_min_s = 10**5
	x_tmp = x
	for si in s_list_i:
		if tmp_min_s > si:
			x_tmp = x_tmp%si
			tmp_min_s = si
			if si == min_s:
				break
	list_x = list_x + x_tmp

tmp=list_x%(10**9+7)
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
n,x=map(int, input().split())
s=sorted(map(int, input().split()))
import fractions,math
ans=0
def fanc1(lista,x1):
    global ans
    if not lista:
        ans+=x1
        return 0
    if x1<lista[0]:
        ans+=(math.factorial(len(lista))*x1)%(10**9+7)
    else:
        for i,j in enumerate(lista):
            fanc1(lista[:i]+lista[i+1:],x1%(s[i]))
fanc1(s,x)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def modsum(x, S):
    if len(S) > 1:
        sum = 0
        for i in range(len(S)):
            #print(S[i], S[:i] + S[i+1:])
            sum += modsum(x % S[i], S[:i] + S[i+1:])
    else:
        sum = x % S[0]
    return sum

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

sum = modsum(X, S)
print(sum % (10**9 + 7))

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


# 黒板にkokubanが書かれているときに i番目以降を適用した場合の答え
@lru_cache(maxsize=2100000)
def amari(i, kokuban):
    if i == n:
        return kokuban
    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:
#! /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
    total.append(x)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import sys
import itertools

input = sys.stdin.readline
a = 1000000007
ans = 0

N, X = map(int, input().split())
s = input().split()
S = list(itertools.permutations(s))
for i in range(len(S)):
    tmp = X
    for j in range(len(S[i])):
        tmp = tmp % int(S[i][j])
    ans += tmp

print(ans % a)

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

# 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)


# 黒板にkokubanが書かれているときに i番目以降を適用した場合の答え
@lru_cache(maxsize=100000)
def amari(i, kokuban):
    if i == n:
        return kokuban
    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:
import math

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

tab = [0] * min(S)

    

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

        if l > min(S):
            ret += f(l, newL)

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


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

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, x = (int(i) for i in input().split())  
s = [int(i) for i in input().split()]

final_ans = 0
for ys in itertools.permutations(s, n):
    blackboard = x
    pre_y = max(s)
    for y in ys:
        if pre_y >= y:
            blackboard = blackboard % y
        else:
            break
    final_ans += blackboard
    
print(final_ans%(pow(10, 9)+7))

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[:]
    s_list_tmp.extend([x % s, s])
    key = tuple(s_list_tmp)
    if key in memo_dict:
        return memo_dict[key]
    if x % s == 0:
        memo_dict[key] = 0
        return 0
    if s == min(s_list):
        value = math.factorial(len(s_list) - 1) * (x % s)
        memo_dict[key] = value
        # print(key, value)
        return value
    s_list2 = s_list[:]
    s_list2.remove(s)
    value = sum([sumD(x % s, s_i, s_list2) % mod for s_i in s_list2])
    memo_dict[key] = value
    # print(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:
MOD = 10**9 + 7

N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
S = [None] + S
dp = [[0 for i in range(X+1)] for j in range(N+1)]
dp[1] = [i % S[1] for i in range(X+1)]
for n in range(2, N+1):
	for x in range(X+1):
		dp[n][x] = (dp[n-1][x] * (n-1) + dp[n-1][x%S[n]]) % MOD
print(dp[N][X])

Submission status: Time Limit Exceeded

Solution code:
import math

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

tab = [0] * min(S)


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

        if l > min(S):
            ret += f(l, newL)

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


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

Submission status: Time Limit Exceeded

Solution code:
n,x = [int(i) for i in input().split()]
s = [int(i) for i in input().split()]

def solve(n,x,s):
    min_s = min(s)
    # if n==0: return 0
    if n==1:
        return x%s[0]
    ans = 0
    mod = [0]*n

    for i,si in enumerate(s):
        mod[i] = x % si

    for i,m in enumerate(mod):
        if m==0: continue
        if m < min_s:
            ans += fact(n-1) * m
            continue
        if m == min_s:
            continue

        s_copy = s.copy()
        del(s_copy[i])

        # isans_0 = False
        # for s_elem in s_copy:
        #     isans_0 = True
        #     if m % s_elem == 0:
        #         print(m,s_elem)
        #         break
        # if isans_0: continue
         
        ans += solve(n-1, m, s_copy)
    return ans % (1e9+7)

def fact(n):
    prod = 1
    for i in range(2,n+1):
        prod *= i
    return prod

print(int(solve(n,x,s) % (1e9+7)))

Submission status: Time Limit Exceeded

Solution code:
n,x = [int(i) for i in input().split()]
s = [int(i) for i in input().split()]

def solve(n,x,s):
    # if n==0: return 0
    if n==1:
        return x%s[0]
    ans = 0
    mod = [0]*n

    for i,si in enumerate(s):
        mod[i] = x % si

    for i,m in enumerate(mod):
        if m==0: continue
        if m < min(s):
            ans += fact(n-1) * m
            continue
        if m == min(s):
            continue

        s_copy = s.copy()
        del(s_copy[i])

        # isans_0 = False
        # for s_elem in s_copy:
        #     isans_0 = True
        #     if m % s_elem == 0:
        #         print(m,s_elem)
        #         break
        # if isans_0: continue
         
        ans += solve(n-1, m, s_copy)
    return ans % (1e9+7)

def fact(n):
    prod = 1
    for i in range(2,n+1):
        prod *= i
    return prod

print(int(solve(n,x,s) % (1e9+7)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import itertools

n, x = (int(i) for i in input().strip().split(' '))
s = [0]*n
for i, si in enumerate(input().strip().split(' ')):
	s[i] = int(si)


s_list = list(itertools.permutations(s))

list_x = 0

for s_list_i in s_list:
	x_tmp = x
	for si in s_list_i:
		x_tmp = x_tmp%si
	list_x = list_x + x_tmp

tmp=list_x%(10**9+7)
print(tmp)

Submission status: Time Limit Exceeded

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

import math
import copy

modu = 1000000007

factorial_table = [0] * 201
for i in range(201):
	factorial_table[i] = math.factorial(i) % modu

def get_residue_sum(a, li, length):
	if a < min(li):
		# 残り全部n
		return a * factorial_table[length]
	elif length == 1:
		return a % li[0]
	else:
		summ = 0
		for idx in range(length):
#			li から iを削除して
			li2 = copy.deepcopy(li)
			q = li2.pop(idx)
			summ += get_residue_sum(a%q, li2, length-1)
		return (summ % modu)

ans = get_residue_sum(X, s, N) % modu
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n, x = map(int, raw_input().split())
ss = sorted(map(int, raw_input().split()))
m1 = {x: 1}
for i in range(n):
    m2 = {}
    for m in m1:
        for j in range(len(ss) - i):
            s = ss[j]
            if s > m:
                m2[m] = (m2.get(m, 0) + m1[m] * (len(ss) - i - j)) % MOD
                break
            v = m % s
            m2[v] = (m2.get(v, 0) + m1[m]) % 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:
import itertools
N, X = map(int, input().split())
S = list(map(int, input().split()))
seq = list(itertools.permutations(S))
#print(seq)
min_S = min(S)
Y = X
m = 0
MOD = 1000000007
for se in seq:
    for i in se:
        X = X % i
        if X < min_S:
            break
    m += X
    m %= MOD
    X = Y
print(m)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N, X = map(int, input().split())
s = list(map(int, input().split()))
num = 10 ** 9 + 7
sum = 0
s_iter = list(itertools.permutations(s))
for k in range(len(s_iter)):
    s_sub = s_iter[k]
    X_sub = X
    for i in range(len(s_sub)):
        X_sub = X_sub % s_sub[i]
    sum += X_sub
print(sum % num)

Submission status: Time Limit Exceeded

Solution code:
import math

def wa(a,bl):
    if a==0:
        return 0
    if min(bl)>a:
        return math.factorial(len(bl))*a
    if len(bl)==1:
        return a%bl[0]
    else:
        re=0
        for b in bl:
            re+=wa(a%b,list(set(bl)^set([b])))
        return re%(10**9+7)

n,a=map(int,input().split())
bl=list(map(int,input().split()))

print(wa(a,bl))

Submission status: Time Limit Exceeded

Solution code:
import itertools

def listExcludedIndices(data, indices=[]):
  return [x for i, x in enumerate(data) if i not in indices]

N, X = [int(i) for i in input().split()]
input_data = [int(i) for i in input().split()]
result = []
sum_x = 0

iter_list = list(itertools.permutations(input_data))
for i in iter_list:
    x = X
    for el in i:
        x = x % el   
    sum_x+=x

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

N, X = map(int,input().split())
S_list = list(map(int,input().split()))
mod = 10**9 + 7

ans = 0

def DFS(x,s_list):
    global ans
    if len(s_list) ==0:
        ans = (ans + x) % mod
    elif x < min(s_list):
        ans = (ans + x*math.factorial(len(s_list))) % mod
    # elif x in s_list:
    #     ans += 0
    else:
        s_list.sort(reverse=True)
        for i,s in enumerate(s_list):
             s_list_after = copy.deepcopy(s_list)
             s_list_after.pop(i)
             x_after = x%s
             DFS(x_after,s_list_after)
    
DFS(X,S_list)
print(ans% mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, X = map(int, input().split())
S = list(map(int, input().split()))
seq = list(itertools.permutations(S))
#print(seq)
min_S = min(S)
Y = X
m = 0
MOD = 1000000007
for se in seq:
    for i in se:
        X = X % i
    m += X
    m %= MOD
    X = Y
print(m)

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
    for y in tpl:
        x = x % y
        if x == 1:
            break
    ans += x

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 math
import copy

modu = 1000000007

def get_residue_sum(a, li, length):
	if a < min(li):
		# 残り全部n
		return a * math.factorial(length)
	elif length == 1:
		return a % li[0]
	else:
		summ = 0
		for idx in range(length):
#			li から iを削除して
			li2 = copy.deepcopy(li)
			q = li2.pop(idx)
			summ += get_residue_sum(a%q, li2, length-1)
		return (summ % modu)

ans = get_residue_sum(X, s, N) % modu
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
# 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()]

MOD = 10**9 +7
ans = 0
memo ={}
def func(S_list,x):
  ans = 0
  if len(S_list)==1:
    return x%S_list[0]
  if (tuple(S_list),x) in memo:
    return memo[(tuple(S_list),x)]
  for s in 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 itertools
import math
n,x = map(int, input().split())
lstS = list(itertools.permutations(list(map(int, input().split())),n))

lstans=[]

for i in range(math.factorial(n)):
    y = x
    for j in range(n):
        y = y % lstS[i][j]
    lstans.append(y)

ans=sum(lstans)%1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, x = [int(item) for item in input().split()]
s = [int(item) for item in input().split()]

sum = 0
xi = x

large_prime = 10 ** 9 + 7
for item in itertools.permutations(s):
    x = xi
    for si in item:
        # print(x, si)
        x = x % si % large_prime
        if x == 0:
            break
    sum += x

print(sum % large_prime)

Submission status: Time Limit Exceeded

Solution code:
n,x = [int(i) for i in input().split()]
s = [int(i) for i in input().split()]

def solve(n,x,s):
    # if n==0: return 0
    if n==1:
        return x%s[0]
    ans = 0
    mod = [0]*n

    for i,si in enumerate(s):
        mod[i] = x % si

    for i,m in enumerate(mod):
        if m==0: continue
        if m < min(s):
            ans += fact(n-1) * m
            continue

        # sの要素で割れたら必ず0？
        # isans_0 = False
        # for s_elem in s:
        #     isans_0 = True
        #     if m % s_elem == 0:
        #         break
        # if isans_0: continue

        s_copy = s.copy()
        del(s_copy[i]) 
        ans += solve(n-1, m, s_copy)
    # print(x,s,ans)
    return ans % (1e9+7)

def fact(n):
    prod = 1
    for i in range(2,n+1):
        prod *= i
    return prod

print(int(solve(n,x,s) % (1e9+7)))

Submission status: Time Limit Exceeded

Solution code:
N, X = [int(i) for i in input().split()]
ls = [int(i) for i in input().split()]
ls = sorted(ls, reverse=True)
min_pos = len(ls) - 1

def dfs(ind, cur):
    if ind ==  min_pos:
        return cur
    _sum = 0
    for next in ls[ind + 1:]:
        _sum += dfs(ind + 1, cur%next)
        _sum %= 1e9+7
    return _sum

print(int(dfs(-1, X)))

Submission status: Time Limit Exceeded

Solution code:
import copy
import math
N,X= map(int, input().split())
S=list(map(int,input().split()))
MOD=int(1e9 + 7)

def modsum(n,x,s):
  #print('modsum'+str(n)+str(x)+str(s))
  if x==0:
    return 0
  elif n==1:
    return x % s[0]
  else:
    mins=min(s)
    if x < mins:
      #print('x:'+str(x)+'n:'+str(n)+'mins:'+str(mins))
      return (x*math.factorial(n))%MOD
    p=0
    for i in range(len(s)):
      s_copy=copy.deepcopy(s)
      s_copy.remove(s[i])
      p += modsum(n-1,x % s[i],s_copy) % MOD
    return p % MOD
  
print(modsum(N,X,S))

Submission status: Time Limit Exceeded

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

sum = 0

def f (x,s):
    global sum
    for i in range(len(s)):
        x2 = x
        if x == s[i]:
            return
        
        if x > s[i]:
            x2 = x%s[i]

        if len(s) > 1:
            sc = s.copy()
            del sc[i]
            f(x2,sc)
        else:
            sum += x2
            return

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

Submission status: Time Limit Exceeded

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

fac_lim = 200
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

ans = 0

def func(n, k, l, p):
    global ans
    if k == 0:
        ans += n*p
        ans %= MOD
    elif k == 1:
        ans += (n%S[0])*p
        ans %= MOD
    else:
        for i in range(k):
            func(n%S[i], i, l-1, divide(p, k))
    return 0

func(X, N, N, fac[N])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n, x = map(int, raw_input().split())
ss = sorted(map(int, raw_input().split()))
m1 = {x: 1}
for i in range(n):
    m2 = {}
    for m in m1:
        for s in ss[:len(ss) - i]:
            v = m % s
            m2[v] = (m2.get(v, 0) + m1[m]) % 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:
import functools
import sys
input = sys.stdin.readline

def solve():
    l, n = map(int, input().split())
    lst = list(map(int, input().split()))
    m, MOD = min(lst), 10**9 + 7
    used = [0 for _ in range(l)]
    p = [1 for _ in range(l + 1)]
    for i in range(2, l + 1):
        p[i] = p[i - 1] * i % MOD
    @functools.lru_cache(maxsize = None)
    def rec(i, n, k):
        if n % lst[i] <= m:
            if n % lst[i] == m:
                return 0
            return (n % lst[i]) * p[k] % MOD
        used[i], ret = 1, 0
        _n = n % lst[i]
        for j in range(l):
            if not used[j]:
                ret = (ret + rec(j, _n % lst[j], k - 1)) % MOD
        used[i] = 0
        return ret
    ret = 0
    for i in range(l):
        ret = (ret + rec(i, n, l - 1)) % MOD
    print(ret)

solve()

Submission status: Time Limit Exceeded

Solution code:
# # # coding=utf-8
# # # Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]


N, X = gets()
Y = sorted(gets())

import bisect
mod = 10**9 + 7


def solve(N, X):
    if not N: return X
    res = 0
    for i in xrange(N):
        y = Y[i]
        X2 = X % y
        N2 = bisect.bisect(Y, X2, hi=N)
        permutation = 1
        for p in xrange(N2 + 1, N):
            permutation = permutation * p % mod
        res = (res + solve(N2, X2) * permutation) % mod
    # print N, X, Y, res
    return res

print solve(N, X)

Submission status: Time Limit Exceeded

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

def solve():
    l, n = map(int, input().split())
    lst = list(map(int, input().split()))
    m, MOD = min(lst), 10**9 + 7
    used = [0 for _ in range(l)]
    p = [1 for _ in range(l + 1)]
    for i in range(2, l + 1):
        p[i] = p[i - 1] * i % MOD
    def rec(i, n, k):
        if n % lst[i] <= m:
            if n % lst[i] == m:
                return 0
            return (n % lst[i]) * p[k] % MOD
        used[i], ret = 1, 0
        _n = n % lst[i]
        for j in range(l):
            if not used[j]:
                ret = (ret + rec(j, _n % lst[j], k - 1)) % MOD
        used[i] = 0
        return ret
    ret = 0
    for i in range(l):
        ret = (ret + rec(i, n, l - 1)) % MOD
    print(ret)

solve()

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
        if x == 1:
            break
    ans_lst.append(x)

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

N, X = map(int,input().split())
S_list = list(map(int,input().split()))
mod = 10**9 + 7

ans = 0

def DFS(x,s_list):
    global ans
    if len(s_list) ==0:
        ans += x
    elif x < min(s_list):
        ans += x*math.factorial(len(s_list))
    elif x in s_list:
        ans += 0
    else:
        for i,s in enumerate(s_list):
             s_list_after = copy.deepcopy(s_list)
             s_list_after.pop(i)
             x_after = x%s
             DFS(x_after,s_list_after)
    
DFS(X,S_list)
print(ans% mod)

Submission status: Time Limit Exceeded

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

fac_lim = 200
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

def func(n, k, l, p):
    ans = 0
    if k == 0:
        ans += n*p
    elif k == 1:
        ans += (n%S[0])*p
    else:
        for i in range(k):
            ans += func(n%S[i], i, l-1, divide(p, k))
    return ans%MOD

print(func(X, N, N, fac[N]))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

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


def search(S, m, X):
    if X < m:
        return (X * fact[len(S)]) % MOD
    ans = 0
    for i in range(len(S)):
        ans = (ans + search(S[:i] + S[i+1:], m, X % S[i])) % MOD
    return ans


def main():
    N, X = map(int, input().split())
    S = list(map(int, input().split()))
    S.sort()
    m = min(S)
    ans = search(S, m, X)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# # # coding=utf-8
# # # Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]


N, X = gets()
Y = sorted(gets())


import bisect
mod = 10**9 + 7


def solve(N, X, Y):
    if not Y: return X
    res = 0
    for i, y in enumerate(Y):
        X2 = X % y
        N2 = bisect.bisect(Y, X2)
        permutation = 1
        for p in xrange(N2 + 1, N):
            permutation = permutation * p % mod
        res = (res + solve(N2, X2, Y[:N2]) * permutation) % mod
    # print N, X, Y, res
    return res

print solve(N, X, Y)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
n, x = map(int, input().split())
nums = list(map(int, input().split()))

ans = 0
for groop in permutations(nums):
    tmp = x
    for num in groop:
        tmp = tmp%num
    ans += tmp
print(round(ans%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = frozenset([int(s) for s in input().split()])
NN = 10 ** 9 + 7

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

dp = {}

def f(n, s):
    if (n, s) in dp.keys():
        return dp[(n, s)]

    if n < min(s):
        result = n * fact[len(s)] % NN
    elif len(s) == 1:
        result = n % list(s)[0]
    else:
        result = sum([f(n % si, s - {si}) for si in s if si > n]) % NN
        result = result + sum([f(n % si, s - {si}) for si in s if si <= n]) % NN
    dp[(n, s)] = result
    return result

print(f(X, S))

Submission status: Time Limit Exceeded

Solution code:
import math

def wa(a,bl):
    if min(bl)>a:
        return math.factorial(len(bl))*a
    if len(bl)==1:
        return a%bl[0]
    else:
        re=0
        for b in bl:
            re+=wa(a%b,list(set(bl)^set([b])))
        return re

n,a=map(int,input().split())
bl=list(map(int,input().split()))

print(wa(a,bl)%(10**9+7))

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

fact = [1]*(X+1)
rfact = [1]*(X+1)
for i in range(X):
    fact[i+1] = r = fact[i] * (i+1) % MOD
    rfact[i+1] = pow(r, MOD-2, MOD)

S.sort()
memo = {}
def dfs(i, k):
    key = (i, k)
    if key in memo:
        return memo[key]
    if i == N:
        return k == X
    r = dfs(i+1, k) * i % MOD
    if k <= S[i]:
        for j in range(k, X+1, S[i]):
            r = (r + dfs(i+1, j)) % MOD
    memo[key] = r
    return r
print(sum(x*dfs(0, x)%MOD for x in range(S[0])) % MOD)

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
  res %= mod
print(res%mod)

Submission status: Time Limit Exceeded

Solution code:
import copy
N,X= map(int, input().split())
S=list(map(int,input().split()))
MOD=int(1e9 + 7)

def modsum(n,x,s):
  #print('modsum'+str(n)+str(x)+str(s))
  if x==0:
    return 0
  elif n==1:
    return x % s[0]
  else:
    p=0
    for i in range(len(s)):
      s_copy=copy.deepcopy(s)
      s_copy.remove(s[i])
      p += modsum(n-1,x % s[i],s_copy) % MOD
    return p
  
print(modsum(N,X,S))

Submission status: Time Limit Exceeded

Solution code:
import itertools

def tryall(x, l):
    sum = 0
    for n in itertools.permutations(l):
        t = x
        for i in n:
            t=t%i
            if i == mins:
                break
        # print(t, n, sep="\t")
        sum += t
    return sum

if __name__ == "__main__":
    N, X = map(int, input().split())
    s = [int(n) for n in input().split()]
    mins = min(s)
    print(tryall(X, s) % (10**9 + 7))

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

    def popi(S,i):
        return S[:i] + S[i+1:]
    # 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
        ans = (ans + solve(popi(S,i), new_x)) % mod
    return ans % mod

print( solve(S, X) % mod )

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

MOD = 10**9 + 7


def f(x, s):
    if not s or all(x < y for y in s):
        return x * factorial(len(s)) % MOD
    return sum(f(x % y, s - {y}) for y in s) % MOD


ans = f(X, set(S))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, x = (int(i) for i in input().split())  
s = [int(i) for i in input().split()]

final_ans = 0
for ys in itertools.permutations(s, n):
    blackboard = x
    for y in ys:
        blackboard = blackboard % y
    final_ans += blackboard
print(final_ans%(pow(10, 9)+7))

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
S = frozenset([int(s) for s in input().split()])
NN = 10 ** 9 + 7

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

dp = {}

def f(n, s):
    if (n, s) in dp.keys():
        return dp[(n, s)]

    if n == 1:
        result = fact[len(s)]
    elif n == 0:
        result = 0
    elif len(s) == 1:
        result = n % list(s)[0]
    else:
        result = sum([f(n % si, s - {si}) for si in s]) % NN
    dp[(n, s)] = result
    return result

print(f(X, S))

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]
    if y == 1:
      break

  tmp += y

print(tmp % m)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def tryall(x, l):
    sum = 0
    for n in itertools.permutations(l):
        t = x
        for i in n:
            t=t%i
        # print(t, n, sep="\t")
        sum += t
    return sum

if __name__ == "__main__":
    N, X = map(int, input().split())
    s = [int(n) for n in input().split()]
    print(tryall(X, s) % (10**9 + 7))