//
// Naiwne Potegowanie modulo
//
// www.algorytm.org
// (c)2007 Tomasz Lubinski
//

using System;

namespace npm_cs
{
	/// <summary>
	/// Naiwne potegowanie modularne.
	/// </summary>
	class NPM 
	{
		/// <summary>
		/// calculates a^b mod m
		/// </summary>
		/// <param name="a">a</param>
		/// <param name="b">b</param>
		/// <param name="m">m</param>
		/// <returns>a^b mod m</returns>
		public static int power_modulo(int a, int b, int m)	
		{
			int i;
			int result = a%m;

			for (i=1; i<b; i++) 
			{
				result *= a;
				result %= m;
			}

			return result;
		}

		/// <summary>
		/// The main entry point for the application.
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
			//9688563^458926 mod 71 = 30
			Console.WriteLine("9688563^458926 mod 71 = " + power_modulo(9688563, 458926, 71));

			//12^4 mod 7 = 2
			Console.WriteLine("12^4 mod 7 = " + power_modulo(12, 4, 7));
		}
	}
}