Background

:::info[Problem Background]

The wind in the woods still blew slowly. Shadows of trees swayed and crossed on the ground, like layers of silent ripples moving on water.

Fieren and Hutaruk were still sitting by that complicated route map, arguing in low voices about who won the game just now. One looked serious and thought the other clearly made a mistake at the last step; the other frowned and insisted that kind of move could never win. Small things like this were not rare on a long journey. Especially after being trapped, anything that could temporarily make people forget their anxiety was still worthwhile.

But Frieren did not join them.

She stood quietly to the side, her eyes resting on the lines she had drawn earlier. Those tracks that looked messy and kept circling back to the starting point overlapped again and again on the paper, like some pattern deliberately hidden. To ordinary travelers, this was probably just a headache-inducing route map; but to a mage who had lived for a long time and seen countless ancient spells, many things would reveal their original shape as long as they repeated enough times.

“So that’s how it is.” Frieren said softly.

“Huh?” Fieren looked up.

“This isn’t just a barrier to make people get lost.” Frieren lightly traced a few intersection points on the paper with her fingertip, speaking calmly. “It’s an ancient misdirection spell that uses the entire forest as the spell’s base. The roads we walked weren’t just going in circles—we were moving along the mana circuits it had preset.”

Hutaruk stared at the nearly unreadable map, fell silent for a moment, and finally said honestly, “It sounds amazing, but I didn’t understand at all.”

“In simple terms,” Fieren summarized for him, “this forest itself is part of the mechanism.”

“Yeah, basically.” Frieren closed her notebook, her expression carrying the calm of finally figuring out where the trouble came from. “Now that we know its structure, it’s not hard to break.”

She raised her staff, and a gentle light lit up at its tip. Those mana flows that were scattered through the woods and almost impossible to notice seemed to be straightened into place in an instant by an invisible hand. The wind passed through the treetops; branches and leaves trembled slightly; and the faint sense of sluggishness around them also disappeared, like an old net spread over the forest, with one corner gently lifted.

“All set.” Frieren said.

“...That’s it?” Hutaruk froze.

“Mm.”

She answered as if it were only as casual as brushing a leaf off her shoulder. Before the two could fully react, Frieren had already cast flight magic. Pale golden mana rose under their feet, like quiet glimmers lifting on the surface of water. In the next moment, they left the damp and dark woodland, passed through layers of canopy, and slowly rose above the forest.

The view suddenly opened up.

Looking down from above, the forest that had trapped them looked like a deep green sea, rolling with endless leaves, stretching all the way to the edge of the mountains. And right at the center of this vast sea of trees, the “Sunken Star Archive” sat quietly.

It was a building so old it almost felt timeless. Its tall gray-white outer walls shone with a cold sheen under daylight; domes and spires overlapped each other, as if the starry sky had been frozen and piled into shape. Even from this distance, one could still feel that calm and profound mana, as if for thousands of years it had simply stood there quietly, waiting for those who could truly reach it.

But there were not no obstacles around the archive.

Surrounding the “Sunken Star Archive” were ancient mechanisms that echoed one another. Some looked like stone pillars embedded into the ground; some like ring-shaped stele disks floating in midair; and some were merely spell nodes scattered through the forest, flickering with faint light. Together they formed a huge and precise sealing structure, like stars bowing around the moon, protecting the entire archive tightly at the center.

“What’s that?” Fieren asked softly.

Frieren watched for a while before speaking slowly.

“It’s the ‘Gongchen Sealing Rite’.” She said. “Ancient mages liked this kind of layout. They scatter multiple independent spell nodes around the target, making them echo and complete each other. As long as the sealing rite still keeps a complete linkage, outsiders can’t truly approach the core area.”

Hutaruk frowned, looking at the dense mechanisms below. “So if we want to enter the ‘Sunken Star Archive,’ we have to deal with these first?”

“Mm.” Frieren nodded. “But we don’t need to break all of them.”

Her gaze moved slowly among those mechanisms, as if silently calculating something. Wind swept across the high sky, blowing her silver-white long hair and lightly lifting the edges of her robe. After a moment, she raised her hand and pointed to a few positions.

:::

Problem Description

There are $n$ “Gongchen Sealing Rites” in the forest, numbered $1\sim n$. Between some pairs of “Gongchen Sealing Rites” there are “mana channels,” and these “mana channels” form an undirected simple graph. In addition, each “Gongchen Sealing Rite” $i$ has a magic value $a_i$.

If there exists a path of odd length between two different “Gongchen Sealing Rites” $x,y$, then these two “Gongchen Sealing Rites” cannot be destroyed at the same time; destroying them simultaneously will cause mana disorder.

Note that the path here is defined as a sequence of vertices $\{v_1, v_2, \dots, v_t\}$. For any $i\in[1, t)$, there is an edge between $v_i$ and $v_{i+1}$. Vertices may repeat; in other words, a path is allowed to pass through repeated vertices or edges. The length of a path is the number of edges it passes through, i.e. $t-1$.

To unlock the “Sunken Star Archive,” Frieren needs to choose exactly $k$ out of these $n$ “Gongchen Sealing Rites” to destroy, without causing mana disorder.

For Frieren this is extremely easy, and soon she came up with a new twist. Define:

• $E$ as the number of ways to choose exactly $k$ “Gongchen Sealing Rites” such that the sum of magic values of the chosen “Gongchen Sealing Rites” is even;
• $O$ as the number of ways to choose exactly $k$ “Gongchen Sealing Rites” such that the sum of magic values of the chosen “Gongchen Sealing Rites” is odd.

Frieren wants to know the value of $E^2 - O^2$ modulo $998244353$.

In addition, the empty set is considered valid. If $k=0$, the sum of magic values is considered $0$.

Input Format

The first line contains three integers $n,m,k(1\leq n\leq 3\times 10^5, 0\leq m\leq 3\times 10^5, 0\leq k\leq n)$, representing the number of “Gongchen Sealing Rites,” the number of “mana channels,” and the number that need to be destroyed.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n(-10^9\leq a_i\leq 10^9)$, representing the magic value of each “Gongchen Sealing Rite.”

The next $m$ lines each contain two integers $u,v(1\leq u,v\leq n, u\neq v)$, indicating that there is an undirected “mana channel” between “Gongchen Sealing Rite” $u$ and “Gongchen Sealing Rite” $v$.

The input guarantees there are no multiple edges or self-loops.

Output Format

Output one line with one integer, representing the value of $E^2 - O^2$ modulo $998244353$.

6 5 3
1 2 3 4 5 6
1 2
2 3
4 5
5 6
6 4

3

4 4 2
1 1 2 2
1 2
2 3
3 4
4 1

998244349

Hint

For Sample 1, we need to choose 3 out of 6 “Gongchen Sealing Rites” to destroy. It is not hard to see that $\{1, 2\}$ and $\{2, 3\}$ cannot be selected at the same time because there exists a path of odd length, so within the connected component $\{1, 2, 3\}$, we can only choose $\{1, 3\}$ or other single vertices.

Within the connected component $\{4, 5, 6\}$, choosing any two “Gongchen Sealing Rites” will have a path of odd length, so we can only choose a single vertex.

In summary, the valid choices are $\{1, 3, 4\}$, $\{1, 3, 5\}$, and $\{1, 3, 6\}$. The sums of magic values are $8$, $9$, and $10$, respectively, so $E=2, O=1$, and $E^2-O^2=3$.

For Sample 2, it is not hard to see that only $\{1, 3\}$ and $\{2, 4\}$ are valid choices. The sums of magic values are $3$ and $3$, so $E=0, O=2$, and $E^2-O^2=-4 \equiv 998244349 \pmod{998244353}$.

Translated by ChatGPT 5