4586 - Mod (Challenge)

• Submit
• Status
• Discuss
• Summary

Description

Mod와 똑같은 문제다. 다만 n이 좀 많이 커졌을 뿐

1에 A를 n번 곱한 값을 B로 나눈 나머지를 구해보자.

Input

* Line 1: 입력 갯수 N (1≤N≤100000)

* Line 2~N+1: A, n, B가 공백으로 구분되어 입력된다. (1≤A,B≤10000, 0≤n≤2000000000‬)

Output

* Line 1~N : 1에 A를 n번 곱한 값을 B로 나눈 나머지를 출력한다.

Sample Input

1
2 3 5

Sample Output

3

Hint

Overflow를 조심하세요!

Time Limit도 조심하세요!

* 제목에 Challenge라고 써있는 문제는 연습문제 점수에 포함되지는 않지만 태도점수에 가산점이 있습니다