Simon has a prime number x and an array of non-negative integers a_1, a_2, ..., a_{n}.

Simon loves fractions very much. Today he wrote out number $\frac{1}{x^{a} 1} + \frac{1}{x^{a_{2}}} + \ldots + \frac{1}{x^{a_{n}}}$ on a piece of paper. After Simon led all fractions to a common denominator and summed them up, he got a fraction: $\frac{s}{t}$, where number t equals x^{a}_1 + a_2 + ... + a_{n}. Now Simon wants to reduce the resulting fraction. 

Help him, find the greatest common divisor of numbers s and t. As GCD can be rather large, print it as a remainder after dividing it by number 1000000007 (10^9 + 7).


-----Input-----

The first line contains two positive integers n and x (1 ≤ n ≤ 10^5, 2 ≤ x ≤ 10^9) — the size of the array and the prime number.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (0 ≤ a_1 ≤ a_2 ≤ ... ≤ a_{n} ≤ 10^9). 


-----Output-----

Print a single number — the answer to the problem modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
2 2
2 2

Output
8

Input
3 3
1 2 3

Output
27

Input
2 2
29 29

Output
73741817

Input
4 5
0 0 0 0

Output
1



-----Note-----

In the first sample $\frac{1}{4} + \frac{1}{4} = \frac{4 + 4}{16} = \frac{8}{16}$. Thus, the answer to the problem is 8.

In the second sample, $\frac{1}{3} + \frac{1}{9} + \frac{1}{27} = \frac{243 + 81 + 27}{729} = \frac{351}{729}$. The answer to the problem is 27, as 351 = 13·27, 729 = 27·27.

In the third sample the answer to the problem is 1073741824 mod 1000000007 = 73741817.

In the fourth sample $\frac{1}{1} + \frac{1}{1} + \frac{1}{1} + \frac{1}{1} = \frac{4}{1}$. Thus, the answer to the problem is 1.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
(n, x) = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
sx = sum(arr)
adds = [sx - i for i in arr]
adds.sort()
while adds.count(adds[0]) % x == 0:
	ct = adds.count(adds[0])
	addsok = ct // x
	adds = [adds[0] + 1] * addsok + adds[ct:]
print(pow(x, min(min(adds), sx), 10 ** 9 + 7))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
from math import inf

def main():
	mod = 1000000007
	(n, x) = [int(x) for x in input().split()]
	array = [int(x) for x in input().split()]
	aSum = sum(array)
	degrees = [0] * n
	for i in range(n):
		degrees[i] = aSum - array[i]
	degrees.sort(reverse=True)
	while True:
		current = degrees.pop()
		count = 1
		while len(degrees) > 0 and degrees[-1] == current:
			degrees.pop()
			count += 1
		if count % x == 0:
			for num in range(count // x):
				degrees.append(current + 1)
		else:
			break
	print(pow(x, min(current, aSum), mod))
BUFFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
input = lambda : sys.stdin.readline().rstrip('\r\n')

def print(*args, **kwargs):
	sep = kwargs.pop('sep', ' ')
	file = kwargs.pop('file', sys.stdout)
	atStart = True
	for x in args:
		if not atStart:
			file.write(sep)
		file.write(str(x))
		atStart = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
main()


modulus = 10 ** 9 + 7
(n, x) = list(map(int, input().split()))
s = list(map(int, input().split()))
tot = sum(s)
powers = [tot - x for x in s]
powers.sort(reverse=True)
while True:
	low = powers[-1]
	cnt = 0
	while len(powers) > 0 and powers[-1] == low:
		cnt += 1
		powers.pop()
	if cnt % x == 0:
		cnt = cnt // x
		for n in range(cnt):
			powers.append(low + 1)
	else:
		low = min(low, tot)
		print(pow(x, low, modulus))
		return


(n, x) = map(int, input().split())
t = list(map(int, input().split()))
b = max(t)
k = t.count(b)
r = sum(t)
s = r - b
while k % x == 0:
	b -= 1
	s += 1
	k = k // x + t.count(b)
print(pow(x, min(r, s), 1000000007))


(n, x) = list(map(int, input().split()))
l = list(map(int, input().split()))
from collections import Counter
l.sort()
gcd = sum(l[:n - 1])
m = 10 ** 9 + 7
s = sum(l)
l1 = []
for i in l:
	l1.append(s - i - gcd)
c = Counter(l1)
l2 = []
for i in c:
	l2.append(i)
l2.sort()
z = True
while z:
	z = False
	for i in c.copy():
		a = c[i]
		b = 0
		while a % x == 0 and a != 0:
			z = True
			a //= x
			b += 1
		if z:
			c[i + b] += a
			c[i] = 0
y = l[-1]
for i in c:
	if c[i]:
		y = min(y, i)
gcd += y
print(pow(x, min(s, gcd), m))


def readln():
	return tuple(map(int, input().split()))
(n, x) = readln()
a = readln()
m = max(a)
ans = sum(a) - m
cnt = {}
for v in a:
	cnt[m - v] = cnt.get(m - v, 0) + 1
while True:
	k = min(cnt.keys())
	v = cnt[k]
	c = 0
	while v % x == 0:
		c += 1
		v //= x
	if c:
		cnt[k + c] = cnt.get(k + c, 0) + v
		cnt.pop(k)
	else:
		break
print(pow(x, ans + min(min(cnt.keys()), m), 10 ** 9 + 7))


(n, x) = map(int, input().split())
a = [int(x) for x in input().split()]

def solve(a, s):
	a.append((-1, 0))
	a.sort()
	b = []
	for i in range(1, len(a)):
		if a[i][0] != a[i - 1][0]:
			b.append(a[i])
		else:
			b[-1] = (a[i][0], b[-1][1] + a[i][1])
	for i in range(len(b)):
		t = b[i][1]
		cnt = 0
		while t % x == 0:
			t //= x
			cnt += 1
		b[i] = (b[i][0] + cnt, t)
	z = min(min(b)[0], s)
	if z == 0:
		return 0
	return z + solve([(x[0] - z, x[1]) for x in b], s - z)
s = sum(a)
print(pow(x, solve([(s - x, 1) for x in a], s), 10 ** 9 + 7))


def Solve(x, a_i):
	v = max(a_i)
	count = a_i.count(v)
	A = sum(a_i)
	s = A - v
	while count % x == 0:
		s += 1
		v -= 1
		count += count // x + a_i.count(v)
	return pow(x, min(s, A), 1000000007)
(n, x) = map(int, input().split())
a_i = list(map(int, input().split()))
print(Solve(x, a_i))


modulus = 10 ** 9 + 7

def main():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	total = sum(arr)
	powers = [total - x for x in arr]
	powers.sort(reverse=True)
	while True:
		low = powers[len(powers) - 1]
		cnt = 0
		while len(powers) > 0 and powers[len(powers) - 1] == low:
			cnt += 1
			powers.pop()
		if cnt % x == 0:
			cnt = cnt // x
			for i in range(cnt):
				powers.append(low + 1)
		else:
			low = min(low, total)
			print(pow(x, low, modulus))
			exit(0)
main()


def calc(n, k, a):
	sTot = sum(a)
	biggest = max(a)
	m = 10 ** 9 + 7
	ans = pow(k, sTot - biggest, m)
	dic = {}
	for (i, item) in enumerate(a):
		if biggest - item not in dic:
			dic[biggest - item] = 1
		else:
			dic[biggest - item] += 1
	extraPow = 0
	i = 0
	while dic[i] % k == 0:
		if i + 1 in dic:
			dic[i + 1] += dic[i] // k
		else:
			dic[i + 1] = dic[i] // k
		i += 1
	val = pow(k, min(i, biggest), m)
	return val * ans % m
(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
print(calc(n, k, a))


input_str = input()
(n, x) = (int(input_str.split()[0]), int(input_str.split()[1]))
input_str = input()
a = input_str.split()
s = 0
for i in range(n):
	a[i] = int(a[i])
	s += a[i]
sum_a = [s - a[i] for i in range(n)]
minimum = min(sum_a)
res = pow(x, minimum, 1000000007)
sum_xa = 0
s_new = s - minimum
for i in range(n):
	sum_xa += pow(x, s_new - a[i], 1000000007)
deg = 0
deg_zn = s - minimum
ts = sum_xa
while sum_xa % 1 == 0 and deg_zn:
	sum_xa /= x
	deg += 1
	deg_zn -= 1
if deg:
	res *= pow(x, deg - 1 if sum_xa % 1 != 0 else deg)
print(res % 1000000007)


import sys
import heapq
input = sys.stdin.readline
MOD = int(1000000000.0 + 7)
(n, x) = list(map(int, input().split()))
a = list(map(int, input().split()))
(s, h) = (sum(a), [])
for i in a:
	heapq.heappush(h, s - i)
(p, cnt) = (0, 0)
while h:
	z = heapq.heappop(h)
	if p == z:
		cnt += 1
		if cnt == x:
			heapq.heappush(h, p + 1)
			cnt = 0
	else:
		if cnt > 0:
			print(pow(x, min(p, s), MOD))
			exit()
		cnt = 1
		p = z
print(pow(x, min(p, s), MOD))


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
from collections import deque
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	s = sum(a)
	mn = 10 ** 9 + 1
	for i in range(n):
		mn = min(mn, s - a[i])
	cnt = []
	for i in range(n):
		cnt.append(s - a[i] - mn)
	cnt.sort()
	queue = deque(cnt)
	ans = 1
	while True:
		v = queue[0]
		tmp = 0
		while len(queue) > 0 and queue[0] == v:
			tmp += 1
			queue.popleft()
		if tmp % x != 0:
			mn = min(s, mn + v)
			break
		for j in range(tmp // x):
			queue.appendleft(v + 1)

	def quickpower(v, count, p):
		tmp = 1
		while count:
			if count & 1:
				tmp = tmp * v % p
			v = v * v % p
			count = count >> 1
		return tmp
	ans = ans * quickpower(x, mn, mod)
	print(ans % mod)
main()


import sys
import heapq
(n, x) = list(map(int, sys.stdin.readline().split()))
a = list(map(int, sys.stdin.readline().split()))
s = sum(a)
h = []
for y in a:
	heapq.heappush(h, s - y)
(p, cnt) = (0, 0)
while len(h) > 0:
	z = heapq.heappop(h)
	if p == z:
		cnt += 1
		if cnt == x:
			heapq.heappush(h, p + 1)
			cnt = 0
	else:
		if cnt != 0:
			print(pow(x, min(p, s), 10 ** 9 + 7))
			return
		cnt = 1
		p = z
print(pow(x, min(p, s), 10 ** 9 + 7))


import math
pri = pow(10, 9) + 7
(n, x) = map(int, input().split())
z = list(map(int, input().split()))
sumr = sum(z)
gcd = sumr - max(z)
t = max(z)
ans = z.copy()
for i in range(len(ans)):
	ans[i] = t - ans[i]
ans.sort()
temp = []
count = 1
from heapq import *
temp = []
for i in range(1, len(ans)):
	if ans[i] == ans[i - 1]:
		count += 1
	else:
		temp.append([ans[i - 1], count])
		count = 1
temp.append([ans[-1], count])
pq = []
from collections import *
al = defaultdict(int)
for i in range(len(temp)):
	al[temp[i][0]] = temp[i][1]
	heappush(pq, temp[i][0])
while len(pq):
	se = heappop(pq)
	r = al[se]
	c1 = 0
	while r % x == 0 and r > 0:
		r = r // x
		c1 += 1
	if c1 == 0:
		ty = min(se + gcd, sumr)
		print(pow(x, ty, pri))
		exit()
	elif al[se + c1]:
		al[se + c1] += r
	else:
		heappush(pq, se + c1)
		al[se + c1] = r


MOD = 10 ** 9 + 7

def pow(x, n, MOD):
	if n == 0:
		return 1
	if n % 2 == 0:
		a = pow(x, n // 2, MOD)
		return a * a % MOD
	else:
		a = pow(x, n // 2, MOD)
		return x * a * a % MOD
(n, x) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
s = sum(a)
d = []
for el in a:
	d.append(s - el)
d.sort()
i = 0
gcd = d[0]
c = 0
while i < n and d[i] == gcd:
	c += 1
	i += 1
while c % x == 0:
	c = c // x
	gcd += 1
	while i < n and d[i] == gcd:
		c += 1
		i += 1
if gcd > s:
	gcd = s
print(pow(x, gcd, MOD))


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
biggest = max(a)
exp = total - biggest
hm = a.count(biggest)
while hm % x == 0:
	biggest -= 1
	exp += 1
	hm = hm // x + a.count(biggest)
if exp > total:
	exp = total
print(pow(x, exp, 1000000007))


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	(n, x) = list(map(int, input().split()))
	powers = list(map(int, input().split()))
	summ = sum(powers)
	biggest = max(powers)
	p = summ - biggest
	number_of_powers = powers.count(biggest)
	while number_of_powers % x == 0:
		biggest -= 1
		p += 1
		number_of_powers = number_of_powers // x + powers.count(biggest)
	if p > summ:
		p = summ
	print(pow(x, p, MOD))

def __starting_point():
	for _ in range(1):
		solve()
__starting_point()