{"id":"cd5beebb-6480-4897-a6aa-7b3657b485e7","name":"Modular Fast Exponentiation","description":"1. You are given a number x.\r\n2. You are given another number n.\r\n3. You are required to calculate x raised to the power n mod 10^9 + 7 in logn complexity.","inputFormat":"The first line contains the integer x and n.","outputFormat":"Output an integer in a line containing x^n mod 10^9+7.","constraints":"1 <= x <= 10^9\r\n0 <= n <= 10^9","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.IOException;\r\nimport java.util.Scanner;\r\n\r\npublic class Main {\r\n\tpublic static int xpown(long x, long n, long p) {\r\n\t\t\r\n\t}\r\n\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tStringBuilder sb = new StringBuilder();\r\n\t\t\r\n\t\t\tint x = scn.nextInt();\r\n\t\t\tint n = scn.nextInt();\r\n\r\n int ans = xpown(x,n,1000000007);\r\n\t\t\tSystem.out.println(ans);\r\n\t\t}\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"10 5 ","sampleOutput":"100000\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"086949fa-3c5e-40c6-8a9c-f9be4b400318","name":"Number Theory For Experts","slug":"number-theory-for-experts","type":0},{"id":"9d5a9f10-abf3-450e-b16d-bb7e06f3e80f","name":"Modular Fast Exponentiation","slug":"modular-fast-exponentiation","type":1}],"next":{"id":"910daa87-1899-4fb1-8e06-38ea272e0bd4","name":"Modular C(n,r)","type":1,"slug":"modular-c-n-r"},"prev":{"id":"e7dbeb4b-e828-42af-8a39-8a1d3f4f8c29","name":"Wilsons Theorem","type":1,"slug":"wilsons-theorem"}}}

Modular Fast Exponentiation

1. You are given a number x. 2. You are given another number n. 3. You are required to calculate x raised to the power n mod 10^9 + 7 in logn complexity.

{"id":"cd5beebb-6480-4897-a6aa-7b3657b485e7","name":"Modular Fast Exponentiation","description":"1. You are given a number x.\r\n2. You are given another number n.\r\n3. You are required to calculate x raised to the power n mod 10^9 + 7 in logn complexity.","inputFormat":"The first line contains the integer x and n.","outputFormat":"Output an integer in a line containing x^n mod 10^9+7.","constraints":"1 <= x <= 10^9\r\n0 <= n <= 10^9","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.IOException;\r\nimport java.util.Scanner;\r\n\r\npublic class Main {\r\n\tpublic static int xpown(long x, long n, long p) {\r\n\t\t\r\n\t}\r\n\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\tScanner scn = new Scanner(System.in);\r\n\t\tStringBuilder sb = new StringBuilder();\r\n\t\t\r\n\t\t\tint x = scn.nextInt();\r\n\t\t\tint n = scn.nextInt();\r\n\r\n int ans = xpown(x,n,1000000007);\r\n\t\t\tSystem.out.println(ans);\r\n\t\t}\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"10 5 ","sampleOutput":"100000\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"086949fa-3c5e-40c6-8a9c-f9be4b400318","name":"Number Theory For Experts","slug":"number-theory-for-experts","type":0},{"id":"9d5a9f10-abf3-450e-b16d-bb7e06f3e80f","name":"Modular Fast Exponentiation","slug":"modular-fast-exponentiation","type":1}],"next":{"id":"910daa87-1899-4fb1-8e06-38ea272e0bd4","name":"Modular C(n,r)","type":1,"slug":"modular-c-n-r"},"prev":{"id":"e7dbeb4b-e828-42af-8a39-8a1d3f4f8c29","name":"Wilsons Theorem","type":1,"slug":"wilsons-theorem"}}}
plane

Editor


Loading...

Modular Fast Exponentiation

medium

1. You are given a number x. 2. You are given another number n. 3. You are required to calculate x raised to the power n mod 10^9 + 7 in logn complexity.

Constraints

1 <= x <= 10^9 0 <= n <= 10^9

Format

Input

The first line contains the integer x and n.

Output

Output an integer in a line containing x^n mod 10^9+7.

Example

Sample Input

10 5

Sample Output

100000

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode