Codeforces Round 752 (Div. 1) |
---|
Закончено |
Это произошло 18 октября 2017 года. Shohag, меланхоличная душа, твердо решил, что будет серьезно заниматься спортивным программированием, поскольку оно показалось ему увлекательным. Прошло 4 года, и он счастлив, что выбрал этот путь. Сейчас он создает раунд на Codeforces. Он нашел выдающуюся задачу, но не имеет ни малейшего представления о том, как ее решить. Помогите ему решить финальную задачу раунда.
Вам даны три целых числа $$$n$$$, $$$k$$$ и $$$x$$$. Найдите количество, по модулю $$$998\,244\,353$$$, последовательностей целых чисел $$$a_1, a_2, \ldots, a_n$$$ таких, что выполняются следующие условия:
Последовательность $$$b$$$ является подпоследовательностью последовательности $$$c$$$, если $$$b$$$ может быть получена из $$$c$$$ путем удаления нескольких (возможно, нуля или всех) элементов.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных.
Первая и единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$x$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le k \le 10^7$$$, $$$0 \le x \lt 2^{\operatorname{min}(20, k)}$$$), разделенных пробелами.
Гарантируется, что сумма $$$k$$$ по всем наборам входных данных не превышает $$$5 \cdot 10^7$$$.
Для каждого набора входных данных выведите одно целое число — ответ на задачу.
6 2 2 0 2 1 1 3 2 3 69 69 69 2017 10 18 5 7 0
6 1 15 699496932 892852568 713939942
В первом наборе входных данных допустимыми последовательностями являются $$$[1, 2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$, $$$[2, 3]$$$, $$$[3, 1]$$$ и $$$[3, 2]$$$.
Во втором наборе входных данных единственной допустимой последовательностью является $$$[0, 0]$$$.
Название |
---|