using System;

using System.Linq;

using System.Collections.Generic;

using System.Text;

​

/*

​

**************** This is optimized Solution (Optimized Solution - Recursive Approach) *****************

​

Link: [https://www.scaler.com/academy/mentee-dashboard/class/26767/assignment/problems/201?navref=cl_tt_lst_nm]

Problem Description

​

Implement pow(A, B) % C.

In other words, given A, B and C, Find (AB % C).

​

Note: The remainders on division cannot be negative. In other words, make sure the answer you return is non-negative.

​

Problem Constraints

-109 <= A <= 109

0 <= B <= 109

1 <= C <= 109

​

Input Format

Given three integers A, B, C.

​

Output Format

Return an integer.

​

Example Input

A = 2, B = 3, C = 3

​

Example Output

2

​

Example Explanation

23 % 3 = 8 % 3 = 2

*/                  

public class Program

{

    public static int ComputePowerFnRecursively(int A, int B, int C){

        long answer = 0;

        /*Base Case*/

        if(A == 0) return 0;

        if(B == 0) return 1;

        /*Recurrence Logic */

        if(B % 2 == 0){

            answer = Program.ComputePowerFnRecursively(A, (B / 2), C) % C;

            answer = (answer * answer) % C;

        }else{

            answer = A % C;

            answer = (answer * Program.ComputePowerFnRecursively(A, (B - 1), C) % C) % C;

        }

        return (int)((answer + C) % C);

    }

    public static void Main()

    {

        /*int A = -1;

        int B = 1;

        int C = 20;*/

        /*int A = -4;

        int B = 5;

        int C = 7;*/

        /*int A = -2;

        int B = 5;

        int C = 3;*/

        /*int A = 0;

        int B = 0;

        int C = 1;*/

        /*int A = 2132;

        int B = 0;

        int C = 12;*/

        int A = 71045970;

        int B = 41535484;

        int C = 64735492;

        /*int A = -7;

        int B = 3;

        int C = 5;*/

        int PowerValue = Program.ComputePowerFnRecursively(A, B, C);

        Console.WriteLine("The Power Value is : " + PowerValue);

    }

}