Back To School '19: FFT Fun

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Winnie has a small list v of integers consisting of 2 primes, X and Y. Winnie wants to make the list larger, so Winnie will take two indices i and j\ (1 \le i < j \le |v|) in the list and add v_i \times v_j to the end of the list. She does this operation N times. After the first time, she cannot choose two indices that have been multiplied together before. That is, the pair (i, j) must not have been used before. In addition, she will always take the two indices that multiplies together to yield the smallest value. Winnie is interested by the product of all elements in the final list after the operation is performed N times. Since C++ doesn't have BigInteger for some reason Since this number may be very large, find this number modulo 998\,244\,353.

There will be T test cases.

Input Specification

The first line will contain the integer T\ (T \in \{1, 20\}), the number of test cases.

The next T lines will each contain three integers N, X, Y\ (1 \le N \le 10^{18}, 2 \le X < Y \le 10^9). X and Y are primes.

Output Specification

Output T lines, the i^\text{th} line will contain the answer to the i^\text{th} test case. In particular, on the i^\text{th} line, you should output the product of the integers in the final list, modulo 998\,244\,353.

It may help to know that 998\,244\,353 = 119 \times 2^{23} + 1.


Subtask 1 [10%]

N \le 100

Subtask 2 [25%]

N \le 10^5

Subtask 3 [20%]

X = 2, Y = 3

Subtask 4 [45%]

No further constraints.

Sample Input 1

3 2 3

Sample Output 1


Explanation For Sample 1

The first integer she adds to the list is 6. Then, the smallest product of the elements at two distinct indices that she hasn't used before is 2 \times 6 = 12 (She will choose i=1, j=3). For the last operation, the smallest product is 3 \times 6 = 18 (She will choose i=2, j=3). The final list is [2, 3, 6, 12, 18], and the product of these 5 integers is 7776.

Sample Input 2

10 2 3

Sample Output 2



There are no comments at the moment.