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

using System;

namespace spm_cs
{
	/// <summary>
	/// Szybkie Potegowanie modulo
	/// </summary>
	class SPM
	{

		/// <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_fast(int a, int b, int m) 
		{
			int i;
			long result = 1;
			long x = a%m;

			for (i=1; i<=b; i<<=1) 
			{
				x %= m;
				if ((b&i) != 0) 
				{
					result *= x;
					result %= m;
				}
				x *= x;
			}

			return (int)result;
		}

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

			//12^53 mod 7 = 3
			Console.WriteLine("12^53 mod 7 = " + power_modulo_fast(12, 53, 7));
		}
	}
}