多次元宇宙融合論

그녀가 지향하던 아름다움은 극도로 단순화되고 또한 절제된 것이었다. 때로는 보다 순진하게 생각하자, 그저 추억으로써 회고되는 장면의 나열이 아니리라. 그녀가 추구하던 아름다움은 언제나 관측의 순간, 그것이 연유한 현실과도 독립되어 변하지 않는 미학으로 남는다. 물론 여러가지 모습으로 나타날 수야 있겠다. 한때는 우주적 풍경과 색채로, 한때는 유성과 별의 움직임으로, 한때는 일상적 즐거움에서, 당신 역시 경험했을 그러한 것들 말이다.

경험되는 세계의 복잡성은 이런 믿음을 비웃기라도 하듯, 그 자체로 무한한 가능성이 되기를 자처한다. 흘러가는 모든 순간을 그 순간에 남겨두지 않기에 생기는 모순이다. 그녀는 이로부터 조금 더 자유로웠나보다.

星間 干渉 融解 輪廻 邂逅 再生 ララバイ 幻想 交錯 観測 証明 廻り 眩む

모든 '행성'은 그래프 $G$와 동일한 구조를 가진다. 각 행성은 그래프 $H$의 한 정점에 대응되며, 두 행성 사이의 인접 여부는 $H$에서의 인접 여부로 정해진다. 이들 행성과 그 사이를 연결하는 길들이 이루는 전체 그래프를 '우주'라고 부르자.

보다 엄밀히, 우주 전체의 정점 집합 $V(G)\times V(H)$ 내 임의의 두 정점 $(g,h)$와 $(g',h')$은 다음의 조건 중 하나를 만족할 때, 그리고 그때에만 간선으로 연결된다.

• $h=h'$이고 $gg'\in E(G)$일 때. 이는 하나의 행성 안에서 $G$의 간선을 따라 움직이는 것을 의미한다.
• $g=g'$이고 $hh'\in E(H)$일 때. 이는 행성 안에서의 위치 $g$를 그대로 유지한 채 $H$의 간선을 따라 인접한 행성으로 건너가는 것을 의미한다.

노노카(ノノカ)는 온 우주의 정점들을 하나의 스패닝 트리로 연결하고자 마음먹는다. 그 전에 우주의 규모를 먼저 파악해 보고 싶었던 노노카는, 스패닝 트리를 그리는 방법의 수를 트리가 포함하는 파랑의 개수에 따라 구분하여 세어 보기로 한다. $H$에서 인접한 두 행성 $u$, $v$를 연결하는 각각의 간선 위에는 단 $1$개의 파랑이 존재하며, 이때 $n$개의 파랑을 포함하는 스패닝 트리의 수를 $A_n$으로 정의하자. 이와 같은 방식으로 노노카는 수열 $\{A_n\}: A_0,A_1,A_2 \cdots$를 구성할 수 있다.

그러나 수열 $\{A_n\}$이 길어지는 것이 싫었던 노노카는 $K$개 이상의 파랑이 모인 경우는 고려하지 않기로 한다.

Planets were found for the weak, as Nonoka would say, but Space-farers such as her are more, and comfortable without earth beneath their feet.

...and yet, she finds it as beautiful as ever.

모든 순간이 정말로 포착된 그 순간에 자리잡아 피사체로서의 역할을 다한다면, 당신도 그와 불안정한 궤도를 두 눈에 담아낼 수 있을까. 잊혀진 세계의 실체는 당신의 손을 거쳐 복원되고 그렇기에 끝내 사라진다. 과거 그녀가 구성했던 부분의 투영으로부터, 그녀가 간과했을 전체의 가능성들을 묻고자한다.

입력으로 수열 $\{A_n\}$의 초기 $K$개 항 $A_0,A_1,\cdots,A_{K-1}$이 주어질 때, $\{A_n\}$이 유도될 수 있는 connected complete multipartite graph $H$의 개수를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$K$ $N'$ $N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$ $A_0\ A_1\ \cdots\ A_{K-1}$

이때 정점 쌍 $(u_i, v_i)$가 주어진다는 것은 그래프 $G$에 대하여 두 정점 사이에 간선이 존재함을 의미한다.

모든 것을 추상화된 형상으로 남겨둔 세계는 무제약으로 환원된다. 오직 순간순간의 시각적 인상과 그 포착만을 추구한 그녀의 우주는 결국 쉼없는 정보의 나열로 귀결되었을 뿐이다. 자신의 위치를 가늠할 별자리마저 없는 칠흑의 공간을 원할 이가 얼마나 있을까?

조건을 만족하는 $H$의 개수를 $998\ 244\ 353$으로 나눈 나머지를 출력하여라. (단, $H$의 정점들은 서로 구별되며, 모든 입력에 대해 가능한 $H$가 하나 이상 존재함이 보장된다.)

• $2\le N'\le 1\ 000\ 000$.
• $2\le N\le 400$.
• $1\le M\le \frac{N(N-1)}2$.
• $1\le u_i,v_i\le N$이고 $u_i\ne v_i$이다 ($1\le i\le M$).
• $G$는 undirected simple connected graph.
• $0\le A_i<998\ 244\ 353$이다 ($0\le i<K$).

또한 그래프 $G$의 Laplacian matrix의 eigenvalue $0=\lambda_0<\lambda_1\leq\cdots\leq \lambda_{N-1}$에 대해 다음이 항상 보장된다:

(단, $\lambda_1>0$임을 증명할 수 있다.)