409773: GYM103741 C Diameter
Description
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<2^n}d_{i,j}$$$) modulo $$$998\,244\,353$$$;
- The number of pairs $$$(i,j)\ (0\le i\le j<2^n)$$$ such that $$$d_{i,j}=\max_{0\le x\le y<2^n}d_{x,y}$$$ modulo $$$998\,244\,353$$$.
It is guaranteed that the graph is connected.
InputThe 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$$$.
OutputOutput the two answers in one line separated by a space.
ExamplesInput3 2 0 1Output
2 12Input
6 3 4 0 1Output
6 64Note
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<4$$$.