Wielki diabelski młyn Cosmo Clock 21 jest symbolem Jokohamy i upiększa nocny widok miasta. Miasto ICPC również chce mieć coś podobnego.
Miasto ICPC planuje zbudować oświetlony diabelski młyn z parzystą liczbą gondoli. Każda gondola ma być pomalowana jednym z kolorów z podanego zbioru kolorów do wyboru. Oświetlenie zaplanowano następująco:
Wszystkie gondole są łączone w pary; każda gondola należy do dokładnie jednej pary.
Parę mogą tworzyć tylko dwie gondole tego samego koloru.
Gondole w parze są połączone prostą linią LED oświetlającą koło.
Żadne dwie linie LED nie przecinają się, gdy patrzymy od przodu.
Kolorowanie gondoli jest odpowiednie, jeśli istnieje co najmniej jeden sposób połączenia ich w pary zgodny z planem oświetlenia.
Rysunek C.1. Diabelskie młyny z odpowiednim (po lewej) i nieodpowiednim (po prawej) kolorowaniem
Mając liczbę gondoli i kolorów do wyboru, policz odpowiednie kolorowania gondoli. Ponieważ diabelski młyn się obraca, dwa kolorowania są uznawane za takie same, jeśli pokrywają się po pewnym obrocie. Dwa kolorowania pokrywające się tylko przy oglądaniu z przeciwnych stron są uznawane za różne.
Wejście
Wejście składa się z jednego przypadku testowego w następującym formacie.
$$n\quad k$$
$n$ i $k$ są liczbami całkowitymi od $1$ do $3\times10^6$ włącznie. Liczba gondoli i kolorów do wyboru wynosi odpowiednio $2n$ i $k$.
Wyjście
Wypisz liczbę odpowiednich kolorowań gondoli modulo $998\,244\,353=2^{23}\times7\times17+1$, która jest liczbą pierwszą.
Przykład
Wejście 1
3 2
Wyjście 1
6
Wejście 2
5 3
Wyjście 2
372
Wejście 3
2023 1126
Wyjście 3
900119621
Uwagi
Dla pierwszego przykładowego wejścia istnieje sześć odpowiednich kolorowań pokazanych na rysunku poniżej.
Rysunek C.2. Odpowiednie kolorowania dla $n=3$ i $k=2$