#2173 지구정복

1 s   128 MB  

Description

김고리는 마계에서 유명한 악마다 (하지만 본인은 천사라고 주장한다). 김고리는 악마답게 지구를 정복하기 위해 로봇 KGB(KimGori Bot)을 개발하였는데 이는 스스로 자신을 복제하며 생산할 수 있는 로봇이다. KGB은 파괴력도 좋지만 스스로 생산할 수 있다는 것이 특히 무서운 점이다. KGB은 김고리의 설정에 따라 스스로 K개의 KGB를 복제해낼 수 있다. 단, KGB이 복제하기 위해서는 H분이 걸린다. 그리고 복제를 실행한 KGB는 충전을 해야 하기 때문에 R분동안 작동을 정지한다. 막 만들어진(복제된) KGB들은 바로 복제를 시작한다.

김고리는 이러한 로봇을 만들어 두고 M만큼의 시간이 흘렀을 때, KGB들의 개수를 알고싶지만 생각하기 귀찮다 (지구정복은 KGB들이 알아서 해줄 것이라 믿고 있다). 김고리는 프로그래밍도 할 줄 알기에 KGB의 수를 계산하는 프로그램을 짜려고 했지만 귀찮음으로 인해 포기한다. 하지만 계산은 해보고 싶은 김고리는 계산해준 사람에게 지구정복 시 혜택을 주기로 하였다.

이 혜택의 떡밥을 덥석 물은 당신들은 이 문제를 풀어야 한다. M만큼의 시간이 흘렀을 때, KGB의 개수를 알려주자. 시작 시간은 0분이며 M분이 되었을 때의 KGB의 개수를 출력해주면 된다.

Input

첫 번째 줄에는 테스트케이스 T(1 ≦ T ≦ 100) 가 주어진다.

다음 줄에는 처음 KGB의 수 N(1 ≦ N ≦ 100) 과 남아있는 시간 M(1 ≦ M ≦ 10,000) 이 주어지고, 다음 줄에는 K(1 ≦ K ≦ 60) 와 H(1 ≦ H ≦ M), 그리고 R(1 ≦ R ≦ M) 이 주어진다.

Output

총 KGB의 개수를 출력해준다. 단, 숫자가 매우 클 수 있으므로 1,000,000,001로 나눈 나머지 값을 출력해준다.

Sample Input

Sample Output

3
1 10
2 3 4
1 23
5 5 5
1 31
10 31 1
17
836
11

Source

2014 Ajou Programming Contest, Division 1