TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (4/6)

Submission's AC Ratio

9.3% (4/43)

Description

化學磁牛是一種特異的生物,簡稱磁牛,其面部由Benzo[cd]indole類物質組成,雖然牠們和一般的牛一樣,會因為地磁關係而經常朝向南北[1],然而其原因卻是這種牛本身具有磁性。牠們的前半身為S極、後半身為N極。

有一天,磁牛因為犯蹕被處以罰金,還被判有期徒刑。然而某一天牠從獄中逃脫,往北方距離N的目的「水龍頭」逃跑。(監獄在水龍頭的正南方。)
典獄長很快便發現了這件事,並且決定使用高科技控制這段路的磁場,要把磁牛吸回來。當他們開啟機器時,磁牛已經往北走了K的距離。

但很不幸的,由於控制磁場的機器年久失修,它控制磁場的功能偶爾就會壞掉。對於開機的每一秒鐘,有$p=\frac{A}{B}$的機率機器可以正常工作,$1-p$的機率不能正常工作。
磁牛當然也不是省油的牛(?)。對於機器正常工作的每一秒鐘,磁牛會被磁力往南方拉動一單位距離;然而,對於機器沒有正常工作的每一秒鐘,磁牛都會往北方逃跑一單位距離。

水龍頭是個神聖之地,且有安全的庇護所,一旦磁牛抵達水龍頭,就再也抓不到了。典獄長想要知道如果機器一直保持這種正常工作的機率,不能用磁力把磁牛吸回監獄的機率是多少,以方便他決定要不要派出額外警力追捕磁牛。

[1]:
According to popular folklore, many animals are smarter than they appear. Dogs bark before earthquakes; cattle predict rainfall by sitting on the ground. But cattle may have another hidden talent in telling which way is north.
Small animals such as mole rats living underground are known for the use of magnetism to navigate. Dr. Begall and her colleagues wanted to know whether larger mammals also have the ability to perceive magnetic fields. They investigated this possibility by studying images of thousands of cattle captured on Google Earth, a website that stitches together satellite photographs to produce an image of the Earth’s surface.
Grazing animals are known to orient themselves in a way that minimizes wind chill from the north and maximizes the warmth of the sun when they are cold. The researchers therefore had to study a lot of cows grazing in lots of different places at different times of day, in order to average out these factors and see whether cattle could act like compass needles.
The researchers concluded that cattle do generally orient themselves in a north-south direction. This north-south preference has also been noted in flies, termites and honeybees. But unfortunately, even the high resolution of Google Earth is not powerful enough to tell which end of the cow is its head, and which its tail.
The researchers were therefore unable to answer their research questions of whether cattle prefer to look north or south, and whether that differs in the northern and southern hemispheres.

Input Format

輸入的第一行有一個正整數$T$,代表測試資料筆數。
接下來有$T$行,每一行有四個正整數$N, K, A, B$,分別代表監獄離水龍頭的距離、開始的距離和每秒鐘機器正常工作的機率$p=\frac{A}{B}$。

$T\leq 10^ 4; K<N\leq 10^ {19}; A, B\leq 3\times 10^ 9;\gcd(A,B)=1$

子任務(測資) 額外限制 分數
1 (0~2) $T\leq 2; N,A,B\leq 9$ 6
2 (0~5) $T\leq 2; N\leq 500$ 16
4 (0~8) $T\leq 50; N\leq 10^ 5$ 17
5 (9) $N\leq 100$ 9
6 (0~11) 無限制 52

Output Format

對於每筆測試資料,請輸出一行,包含兩個正整數,以空格隔開。
假設不能把磁牛吸回來的機率最簡分數表示為$\frac{P}{Q}$,請依序輸出P和Q分別模100000007的值。

Sample Input

1
6 1 1 3

Sample Output

32 63

Hints

Problem Source

改編自建中數學校內培訓(推廣)
Problem set / description by Yihda Yol
建國中學105學年度校內第四次模擬賽pA

Subtasks

For Testdata: 0 ~ 2, Score: 6
For Testdata: 0 ~ 5, Score: 16
For Testdata: 0 ~ 8, Score: 17
For Testdata: 9 ~ 9, Score: 9
For Testdata: 0 ~ 11, Score: 52
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 65536 262144
1 900 65536 262144
2 900 65536 262144
3 900 65536 262144
4 900 65536 262144
5 900 65536 262144
6 900 65536 262144
7 900 65536 262144
8 900 65536 262144
9 900 65536 262144
10 100 20480 262144
11 100 20480 262144