Brute-Force Attack

문제 정보

    • 문제 ID
    • 시간 제한
    • 메모리 제한
    • 제출 횟수
    • 정답 횟수 (비율)
    • 출제자
    • 출처
    • 분류

문제

암호학에서 Brute-Force Attack 은, 암호를 풀기 위해서 무식하게 수많은 암호를 하나하나 시도하는 방법을 일컫는다. 대부분의 경우 Brute-Force Attack 을 사용하는 것은 무의미하지만, 시스템이 허용하는 암호의 수가 제한되어 있다면 Brute-Force Attack 이 유용할 수도 있다.

예를 들어, 은행 비밀번호는 항상 4자리의 10진수로 구성되어 있기 때문에 10000개의 암호 조합만이 사용 가능하다.

당신은 어떤 시스템의 암호를 Brute-Force Attack 으로 알아내고 싶다. 이 시스템에서 최소 A자리에서 최대 B자리의 암호를 사용할 수 있다고 하며, 암호의 각 자리에는 N종류의 글자 중 하나를 사용할 수 있다고 하자. (예를 들어, 은행의 비밀번호에 대해서는 A=B=4, N=10 이다.) 이 때 이 시스템에서 사용할 수 있는 암호 조합의 수를 계산하는 프로그램을 작성하라.

답이 클 경우, 1000000007 의 나머지만을 출력한다.

입력

입력의 첫 줄에 테스트 케이스의 개수 C (<= 100) 가 주어진다. 그 후 C줄에 각각 A 와 B, N 이 세 개의 자연수로 주어진다. (1 <= A <= B <= 100 000 000, 1 <= N <= 128)

출력

각 테스트 케이스마다, 시스템에서 사용할 수 있는 암호 조합의 수를 1000000007 로 나눈 나머지를 한 줄에 출력한다.

예제 입력

4
1 100000 1
4 4 10
4 8 36
3567404 46749457 21

예제 출력

100000
10000
712979373
278986658

노트

3개의 댓글이 있습니다.