about summary refs log tree commit diff
path: root/codechef/gdsub.py
diff options
context:
space:
mode:
authorNguyễn Gia Phong <vn.mcsinyx@gmail.com>2019-09-16 20:32:51 +0700
committerNguyễn Gia Phong <vn.mcsinyx@gmail.com>2019-09-16 20:32:51 +0700
commit4b8df7227736b7c41af56e053d40decc309fe7f9 (patch)
tree9d2823886c29ddd3ac8cd8a5503ad130238d012e /codechef/gdsub.py
parent029688e143109344989b1529259e391822abb0aa (diff)
downloadcp-4b8df7227736b7c41af56e053d40decc309fe7f9.tar.gz
Recovery (2010)
Diffstat (limited to 'codechef/gdsub.py')
-rwxr-xr-xcodechef/gdsub.py18
1 files changed, 18 insertions, 0 deletions
diff --git a/codechef/gdsub.py b/codechef/gdsub.py
new file mode 100755
index 0000000..56c6a84
--- /dev/null
+++ b/codechef/gdsub.py
@@ -0,0 +1,18 @@
+#!/usr/bin/env python3
+from collections import Counter
+from functools import reduce
+
+def mod(n): return n % 1_000_000_007
+
+def cha1n(iterable):
+    yield 1
+    yield from iterable
+
+n, k = map(int, input().split())
+counts = tuple(Counter(map(int, input().split())).values())
+if len(counts) <= k:
+    print(reduce(lambda x, y: mod(x * (y+1)), counts, 1))
+else:
+    s = [0] * k
+    for c in counts: s = [mod(x + y*c) for x, y in zip(s, cha1n(s))]
+    print(mod(sum(s, 1)))