1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#!/usr/bin/env python3
from fractions import Fraction
from functools import reduce
from math import factorial
from operator import floordiv, mul
class Polynomial:
"""A fixed-length power series class.
The Polynomial class is made to calculate the number of permutations
and combinations using generating function, so it only provides '+',
'*', '**' methods and doesn't support negative power degrees.
Parameters
----------
coef : iterable of numeric objects
Polynomial coefficients in order of increasing degree, i.e.,
``(1, 2, 3)`` give ``1 + 2*x + 3*x**2``.
length : int
Maximum length for coef
"""
MAXLEN = 1001
def __init__(self, coef, length=None):
self.coef = list(coef)[:(length or Polynomial.MAXLEN)+1]
def __len__(self):
"""Return len(self)."""
return len(self.coef)
def __getitem__(self, term):
"""Return coefficient of the corresponding term."""
try:
return self.coef[term]
except IndexError:
return 0
def __iter__(self):
return iter(self.coef)
def __repr__(self):
return 'Polynomial({})'.format(self.coef)
def __add__(self, value):
"""Return self+value."""
length = max(len(self), len(value))
return Polynomial((self[i]+value[i] for i in range(length)))
def __mul__(self, value):
"""Return self*value."""
if isinstance(value, Polynomial):
l = []
for i in range(min(len(self) + len(value) - 1, Polynomial.MAXLEN)):
l.append(sum(value[i - j] * c for j, c in enumerate(self)
if 0 <= i - j < len(value)))
return Polynomial(l)
if isinstance(value, (int, float, complex, Fraction)):
return Polynomial((i * value for i in self.coef))
err = "unsupported operand type(s) for *: 'Polynomial' and '{}'"
raise TypeError(err.format(type(value).__name__))
def __rmul__(self, value):
"""Return value*self."""
return self * value
def __pow__(self, value):
"""Return self**value."""
if value == 1: return self
tmp = self ** (value//2)
if value % 2: return tmp * self * tmp
return tmp * tmp
class ExpPoly(Polynomial):
"""Exponential polynomial, with highest degree of 1000."""
EXPPOLY = Polynomial((Fraction(1, factorial(i)) for i in range(Polynomial.MAXLEN)))
def __init__(self, degree):
Polynomial.__init__(self, ExpPoly.EXPPOLY.coef, length=degree)
def chonso(m, a):
t = tuple(min(a.count(i), m) for i in set(a))
d = {i: t.count(i) for i in set(t)}
Polynomial.MAXLEN = m + 1
g = (ExpPoly(k) ** v for k, v in d.items())
return reduce(mul, g, factorial(m))[-1].numerator
if __name__ == '__main__':
with open('chonso.inp') as fi, open('chonso.out', 'w') as fo:
n, m = map(int, fi.readline().split())
a = tuple(int(i) for i in fi.readline().split())[:n]
print(chonso(m, a) % (10**12 + 7), file=fo)
|
