P14759 [Opoi 2025] CCD 的异或 II

CCD 仍然喜欢异或，尤其喜欢在一个序列上玩游戏，但是由于 CCD 不够聪明，无法解出序列上的问题，这次他找到了你，寻求你的帮助。

你需要构造一个长度为 $n$ 的 01 序列 $A$。 这个序列要满足 $m$ 个限制。每个限制都形如二元组 $(l,r)$，表示从 $A_l$ 到 $A_r$ 的异或和需要等于 $1$。 你需要输出满足所有限制的构造方案数对 $998244353$ 取模的结果，并构造方案中字典序最小的 $A$。

第一行输入两个整数 $n,m$。 接下来 $m$ 行，每行输入两个整数 $l,r$，表示一个限制。

第一行输出满足所有限制的构造方案数对 $998244353$ 取模的结果。 如果方案数不为 $0$，请在第二行输出一个 01 串，表示构造方案中字典序最小的 $A$。

**本题采用捆绑测试。** $$ \def\arraystretch{1.2} \begin{array}{|c|c|c|c|} \hline \begin{array}{c} \tt{subtask}\\\hline 1\\\hline 2\\\hline 3\\\hline 4\\\hline \end{array} & \begin{array}{c} n,m\\\hline \le 10^6\\\hline \le 20\\\hline \le 5\times10^3\\\hline \le 10^6\\\hline \end{array} & \begin{array}{c} \textrm{特殊性质}\\\hline m=0\\\hline \\ \textrm{无}\\ \\\hline \end{array} & \begin{array}{c} \tt{pts}\\\hline 5\\\hline 15\\\hline 30\\\hline 50\\\hline \end{array} \\\hline \end{array} $$ 对于所有数据，$\forall 1\le i \le m,1 \le l_i \le r_i \le n$。