Implement Shamir's Secret Sharing reconstruction Shamir's secret sharing scheme is a simple way of protecting a secret by splitting it into several parts needed to reconstruct it.

Your task is to implement Shamir's Secret Sharing reconstruction over the Finite Field defined by the prime 1928049029. If you have any doubts about what this means, just ask or see Finite Field &amp; Finite Field Arithmetic in wikipedia (more resources below).

Input

Input is done using stdin. First comes an integer k, then k lines follow. Each of these lines contains a pair of integers x y that represent a secret. In other words f(x) = y in the original polynomial that was used to construct the secrets.

The number of secrets given is always enough to construct the corresponding secret.

Output

Output to stdout the reconstructed secret.

Examples

Input:

5         
1 564797566
2 804114535
4 1354242660
6 1818201132
7 503769263


Output:

1234


Input:

7
1 819016192
2 1888749673
3 1737609270
4 365594983
5 1628804870
6 1671140873
7 492602992


Output:

456457856


Resources

Wikipedia article

Paper

Finite field Source: Wikipedia

Finite field arithmetic Source: Wikipedia

Lagrange polynomial Source: Wikipedia

Chapter on Finite field arithmetic
bash, 271 chars

r(){
[ ${1/0/} ]&&{ r $(($2%$1)) $1;((t=u,u=v-$2/$1*u,v=t));}
}
read
((N=1928049029,n=0))
while read x[$n] y[$n]
do((n++))
done
for((i=n;z=(z+l)%N,i--;))do
for((j=n,l=y[i];j--;))do
((u=0,v=1,d=x[j]-x[i],M=N+d))
r M N
[ ${d/0/} ]&&((l=l*x[j]%N*(u+N)%N))
done
done
echo $z

The newlines could be replaced in most cases with semicolons, but I don't think there's any unnecessary whitespace.

(I hadn't realised before today that bash's integers are 64-bit - very helpful).

For bash the recursive GCD (exploiting global state) seems to be more compactible than the iterative one. This is mostly straightforward; the interesting trick is [ ${d/0/} ]&amp;&amp;foo which is effectively if [ $d -ne 0 ];then foo;fi