#!/usr/bin/env python -i

from random import SystemRandom

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a, m):
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse for '+str(a)+' modulo '+str(m)+
			' does not exist')
	else:
		return x % m

def share(p, a, n, t):
	rand = SystemRandom()
	c = [rand.randrange(p) for i in range(1, t)]
	s = []
	for i in range(1, n+1):
		 s.append([i, a])
		 for j in range(1, t):
		 	s[i-1][1] = (s[i-1][1] + c[j-1]*(i**j)) % p
	
	return s
	
def reconstruct(p, n, t, s):
	if len(s)<t:
		return False
	I = [r[0] for r in s]
	u = []
	for i in I:
		ui = 1
		for j in I:
			if j != i:
				ui = (ui * (0-j) * modinv((i-j) % p, p)) % p
		u.append(ui)
	
	sum = 0
	for si, ui in zip(s, u):
		sum = (sum + si[1]*ui) % p
		
	return sum
	
	
	
	
	
	
	# c = [166, 94] # with p = 1613; n = 6; t = 3; a = 1234
	# c = [19, 21] # with p = 31; n = 8; t = 3; a = 7