409773: GYM103741 C Diameter

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.

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 the two answers in one line separated by a space.

3 2
0 1

2 12

6 3
4 0 1

6 64

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$$$.