#ifndef MOD_H
#define MOD_H
template <int p> class Mod 
{
 private: int v;  // 0<=v<=p-1
 public:
   Mod(){v=0;}
   Mod(int i){ v=(i>=0?i%p:(i%p)+p) ;}

   Mod<p> operator+(Mod<p>n)const { return Mod<p>(v+n.value());}
   Mod<p> operator-(Mod<p>n)const { return Mod<p>(v-n.value());}
   Mod<p> operator*(Mod<p>n)const { return Mod<p>(v*n.value());}
   Mod<p> square()const { return *this * *this ;}
   Mod<p> pow(Mod<p> n)const;

   // Mod<p> operator/(Mod<p>n)const { to be done?? }

   int value()const{ return v;}
};
template <int p> Mod<p> Mod<p>::pow(Mod<p> n0)const 
{ 
	Mod<p> m(v); // squares of this number
	int n=n0.value();
	Mod<p> w(1); //working value of power

	while(n>0) // invariant (*this).pow(n0) = w * m.pow(n).
	{
		if( n % 2 == 0 )  // so that n is 2*k or equivalently
					// k is n/2.
		{
			m = m.square();
			n = n/2;
		}
		else // n is odd and 2*k+1
		{
			w = w * m;
			n--;
		}
	} // n==0
	return w;
}
#endif