C-- 프로그램

면접 대비

시간 제한1초메모리 제한128 MB

요약

1부터 M까지 시작값 중 덧셈, 뺄셈, 곱셈, 내림 나눗셈 명령을 차례로 실행해 정확히 A에 도달하는 개수를 셉니다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 구간, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

헥토르는 최근에 프로그래밍 언어 C--를 배우기 시작했습니다. 이 언어의 프로그램은 명령을 실행하기 전에 메모리에 저장된 하나의 자연수 변수를 대상으로 동작합니다.

C--에서는 다음 명령을 사용할 수 있습니다.

+= X : 메모리의 변수에 $X$ 를 더합니다.
-= X : 메모리의 변수에서 $X$ 를 뺍니다.
*= X : 메모리의 변수에 $X$ 를 곱합니다.
/= X : 메모리의 변수를 $X$ 로 나눕니다. 나눗셈은 몫만 취하는 정수 나눗셈(내림)입니다.

헥토르는 C-- 프로그램을 작성했고, 실행이 끝난 뒤 메모리 변수의 값이 $A$ 가 되기를 원합니다. 구간 $[1, M]$ 안의 초기값 중에서 이를 만족시키는 값은 몇 개입니까?

입력

첫째 줄에 테스트 케이스의 수 $Z$ ( $1 \le Z \le 10$ )가 주어집니다.

각 테스트 케이스의 첫째 줄에는 정수 $N$ , $M$ , $A$ ( $1 \le N \le 1000$ , $1 \le M \le 10^{18}$ , $0 \le A \le 10^{18}$ )가 주어집니다. 이어지는 $N$ 개의 줄에는 프로그램의 명령이 순서대로 주어지며, 각 명령의 $X$ 는 $1 \le X \le 10^{18}$ 을 만족합니다.

각 명령을 실행한 뒤의 변수 값은 항상 부호 있는 64비트 정수(signed long long) 범위에 들어가며 음수가 되지 않는다고 가정해도 됩니다.

출력

각 테스트 케이스마다 문제의 조건을 만족하는 초기값의 개수를 한 줄에 하나씩 출력합니다.

예제4

예제 1
입력
```
2
1 6 1
/= 3
2 10 4
+= 2
*= 3
```
예상 출력
```
3
0
```
예제 2
입력
```
1
1 10 7
+= 3
```
예상 출력
```
1
```
예제 3
입력
```
1
1 100 15
*= 5
```
예상 출력
```
1
```
예제 4
입력
```
1
1 20 2
/= 4
```
예상 출력
```
4
```