In a graph with $s$ vertices, there are $s-n$ edges that form $n$ connected components, where the $i$-th connected component contains $a_i$ vertices.

We need to add $n-1$ edges to make the graph a tree. For a given configuration of added edges, let $d_i$ be the number of edges connected to the $i$-th component in the original graph. The value of this tree $T$ is defined as:

$$ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right) $$

Your task is to calculate the sum of the values of all possible spanning trees, modulo 998244353.

Input

The input is read from standard input.

The first line contains two integers $n$ and $m$, as described in the problem statement.

The next line contains $n$ integers, where the $i$-th integer represents $a_i$ $(1\le a_i< 998244353)$.

• You can calculate the total number of vertices $s$ from $a_i$, so $s$ is not provided in the input.

Output

Output to standard output.

The output contains a single integer representing the answer.

Examples

Input 1

3 1
2 3 4

Output 1

1728

Note 1

Let $i$ denote the original connected component of size $i$. There are three possible ways to connect the components:

2 - 3 - 4
3 - 2 - 4
2 - 4 - 3

The sum of values is:

$$ \left(2\times 3^2\times 4\times 2+3\times 2^2\times 4 \times 2+2\times 4^2\times 3\times 2\right)\times (1+2+1)=1728 $$

Input 2

233 10
604230822 258609018 347836125 103063600 545593375 983656639 636383432 149579311 37952830 782185282 792399760 556879020 19276539 821164472 992758005 635410231 174811932 967712405 76287574 877354238 403371989 131233662 90928781 909518950 816498283 460305280 688669184 272529638 706529895 931734844 376928193 161521421 41104566 573769373 264585020 586697940 408186715 749973507 585282307 446139544 533914437 228442770 4774211 553190975 51362889 997532216 39361909 75179876 816005324 115649482 801539169 70138016 95888199 892467950 979656965 761391537 354528877 519086852 35676822 910063828 301582400 261610070 73340896 342686965 835379442 186930971 778389960 245321804 936904477 365427914 691461347 321579617 593870684 545240614 874770591 494238628 393533533 914132499 418423560 211294504 878787036 221718376 281432519 823680290 115941973 111850187 435832530 319475906 630937038 471509352 80300437 932519437 733119421 153641332 125967105 419259567 340572302 904357065 664581370 128237482 120545682 206803421 449817099 563421421 752044034 175348393 59415697 147333214 91236540 326844312 207632773 819028631 548562687 338070347 493469625 513509716 449920533 929302154 681990677 929862626 251572209 762291113 713142767 833696686 915932444 839109871 254711900 107265449 594227639 768298325 235502930 563778377 975101745 685320028 128955445 577906482 860668421 37376197 574244751 800910016 364220508 630882579 470699350 761788251 968952925 813174030 126058670 269634161 593236888 808049346 201252435 844809096 572096106 914395201 529266485 338789253 604265775 783978384 295059757 49254118 403037413 530562686 613032494 228899861 66643418 590992994 806806343 776316894 628369191 231811797 427987613 841594754 862694376 898686962 605138652 682408004 562621696 731197321 952042165 157614231 390007370 4055303 851428382 962103475 918450503 382450515 151653431 373476981 17189602 446713187 271736154 420227014 826280929 884768647 649126875 892924346 326522345 306693921 520001943 954891535 387510773 947989555 647246992 100965852 697437220 103146348 783373856 261814563 834343668 737171668 268433849 75111742 741226970 121617879 38970864 510438176 353073449 39629351 732920212 370263050 335347593 6412014 639495120 163384169 740185716 139382698 905313570 68463708 446076618 427071160 872360298 833587390 225821418

Output 2

521800668

Constraints

There are 20 test cases in this problem, each worth 5 points.

• 20% of the data: $n\le 500$.
• Another 20% of the data: $n\le 3000$.
• Another 10% of the data: $n\le 10000, m=1$.
• Another 10% of the data: $n\le 10000, m=2$.
• Another 20% of the data: all $a_i$ are equal.
• 100% of the data: $n\le 3\times 10^4, m\le 30$.

Each subset of test cases has a certain gradient.