C. Diameter
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$ and a set $$$S\subseteq\{0,1,\dots,n-1\}$$$ with $$$m$$$ integers. A graph with $$$2^n$$$ vertices labelled from $$$0$$$ to $$$2^n-1$$$ is built in the following way: for each $$$s\in S$$$ and $$$i\in \{0,1,\dots,2^n-1\}$$$, connect vertex $$$i$$$ and $$$(i+2^s)\text{ mod }2^n$$$ with an undirected edge of length $$$1$$$.

Let $$$d_{i,j}$$$ be the distance between vertex $$$i$$$ and $$$j$$$, and you need to answer:

  • The diameter of the graph (i.e., $$$\max_{0\le i\le j \lt 2^n}d_{i,j}$$$) modulo $$$998\,244\,353$$$;
  • The number of pairs $$$(i,j)\ (0\le i\le j \lt 2^n)$$$ such that $$$d_{i,j}=\max_{0\le x\le y \lt 2^n}d_{x,y}$$$ modulo $$$998\,244\,353$$$.

It is guaranteed that the graph is connected.

Input

The first line contains two integers $$$n\ (1\le n\le 10^6)$$$ and $$$m\ (1\le m\le n)$$$ as described above.

The second line contains $$$m$$$ integers, the elements in set $$$S$$$.

Output

Output the two answers in one line separated by a space.

Examples
Input
3 2
0 1
Output
2 12
Input
6 3
4 0 1
Output
6 64
Note

The graph built in the first example is as below.

The diameter of the graph is $$$2$$$, and there are $$$12$$$ pairs of vertices with distance $$$2$$$: $$$(i,i+3)$$$, $$$(i,i+4)$$$, $$$(i,i+5)$$$ for all $$$0\le i \lt 4$$$.