#include <stdio.h>
#include <string.h>

int prime[10000];

//素数表
int primelist(int n)
{
	int m=1,i,j;
	prime[0]=2;
	for(i=3;i<=n;i+=2){
		for(j=0;j<m&&prime[j]*prime[j]<=i;j++) if (i%prime[j]==0) break;
		if (j>=m||i%prime[j]!=0) prime[m++]=i;
	}
	return m;
}

//扩展的欧几里得算法，输入a,b，返回最大公约数d，并且ax+by=d
int extended_euclid(int a,int b,int &x,int &y)
{
	int d,temp;
	if (b==0){
		x=1,y=0;
		return a;
	}else{
		d=extended_euclid(b,a%b,x,y);
		temp=x;
		x=y;
		y=temp-a/b*y;
		return d;
	}
}

//求a^b mod n
int modular_exponent(int a,int b,int n)
{
	int t=1,y=a;
	while(b!=0){
		if (b&1) t=t*y%n;
		y=y*y%n;
		b>>=1;
	}
	return t;
}

//解线性同余方程ax=b(mod p)，返回最小的x
int solve_equation(int a,int b,int p)
{
	int d,x,y;
	d=extended_euclid(a,p,x,y);
	if (b%d!=0) return -1;
	x*=b/d;
	x=(x%(p/d)+p/d)%(p/d);
	return x;
}

//中国剩余定理，解同余方程组a=b[i](mod p[i])
int modular_equations(int b[],int p[],int n)
{
	int a=0,i,m=1,x,y,t;
	for(i=0;i<n;i++) m*=p[i];
	for(i=0;i<n;i++){
		t=m/p[i];
		extended_euclid(p[i],t,x,y);
		a=(a+t*y*b[i])%m;
	}
	return (a+m)%m;
}

int main()
{
	int b[3]={1,4,6},q[3]={3,5,7};
	printf("%d\n",modular_equations(b,q,3));
	return 0;
}