From the Problem Setter

・This problem differs from Problem C only in the constraints and the time limit.
・AC has been confirmed with python and pypy, but in slow languages your solution may not finish in time, depending on the implementation.

Problem Statement

When a sequence $v=(a_1,a_2,a_3)$ consisting of 3 elements satisfies the following conditions, $v$ is traditionally said to be a Kadomatsu sequence.
1.$a_1,a_2,a_3$ are all distinct
2.Among the 3 elements, $a_2$ is the largest or the smallest
Furthermore, for a sequence $ w=(a_1,a_2....,a_n)$ consisting of $n$ elements (where $3≦n$),
if any 3 consecutive elements taken from it form a Kadomatsu sequence, $w$ is called a Kadomatsu sequence sequence.

There are $K^N$ integer sequences of length $N$ in which each element is at least $0$ and less than $K$. Suppose that $ans_1$ of them are Kadomatsu sequence sequences. Output $ans_1$ modulo $998244353$.
Furthermore, compute the sum of each sequence over all $ans_1$ Kadomatsu sequence sequences, and let $ans_2$ be the total of these sums. Output $ans_2$ modulo $998244353$.

Input

$N\ K$

$3≦N≦10^9$
$3≦K≦9$
$N,K$ are integers.

Output

Output $ans_1$ and $ans_2$, each modulo $998244353$, separated by a single space.
Print a newline at the end.

Sample

3 3

4 12

6 9

26124 626976

75432 9

27800053 805337678