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/28336/assignment/problems/9314?navref=cl_tt_lst_nm]

Problem Description

​

Given two Integers A, B. You have to calculate (A ^ (B!)) % (1e9 + 7).

​

"^" means power,

​

"%" means "mod", and

​

"!" means factorial.

​

Problem Constraints

1 <= A, B <= 5e5

​

Input Format

First argument is the integer A

​

Second argument is the integer B

​

Output Format

Return one integer, the answer to the problem

​

​

​

Example Input

Input 1:

​

A = 1

B = 1

Input 2:

​

A = 2

B = 2

​

​

Example Output

Output 1:

​

1

Output 2:

​

4

​

​

Example Explanation

Explanation 1:

​

 1! = 1. Hence 1^1 = 1.

Explanation 2:

​

 2! = 2. Hence 2^2 = 4.

*/                  

public class Program

{

    public static int ComputePowerFnRecursively(int A, int B, double 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) % (long)C;

            answer = (answer * answer) % (long)C;

        }else{

            answer = A % (long)C;

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

        }

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

    }

    private static int FindFactorialRecursively(int num){

        long mod = (long)1e9 + 7;

        //Sanity Case

        if(num < 0){

            return int.MinValue;

        }

        //Base Case

        if(num == 1){

            return 1;

        }

        //Recurrence Relation Logic

        return (int)(num % (mod - 1) * Program.FindFactorialRecursively(num - 1) % (mod - 1));

    }

    public static void Main()

    {

        /*int A = 6;

        int C = 23;

        int B = (C - 2);*/

        /*int A = 2;

        long C = (long)(1e9 + 7);

        int B = 8;*/

        int A = 35;

        long C = (long)(1e9 + 7);

        int B = 68;

        /*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 factVal = Program.FindFactorialRecursively(B);

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

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

    }

}