After getting tired of the buns and eggs in the student cafeteria, you no longer want to eat them for breakfast and decide to eat strings instead. A string contains only lowercase English letters and is 1-indexed.
A string $S$ is "delicious" if and only if it contains exactly $m$ "egg" subsequences. An "egg" subsequence is an array of 3 indices $a_1, a_2, a_3$ such that $1 \le a_1 < a_2 < a_3 \le |S|$ and $S_{a_1}S_{a_2}S_{a_3}$ is "egg".
The value of a string $T$ is defined as the number of substrings $T[l, r]$ that are delicious. Two substrings are considered different if and only if their positions are different.
There is a string of length $n$ in the cafeteria, where each character is generated independently and randomly. The probability that the $i$-th character is the $i$-th lowercase letter is $p_i$.
You want to know the expected value of this string modulo $998\,244\,353$.
Input
The first line contains two positive integers $n, m$ ($1 \le n \le 5 \times 10^5$, $1 \le m \le 1500$), representing the length of the string and the required number of "egg" subsequences, respectively.
The second line contains 26 integers $p_1, p_2, \dots, p_{26}$ ($0 \le p_i < 998\,244\,353$), representing the probabilities. It is guaranteed that $\sum_{i=1}^{26} p_i \equiv 1 \pmod{998\,244\,353}$.
Output
Output a single integer representing the expected value of the string modulo $998\,244\,353$. It is guaranteed that the answer can be expressed in the form $x \cdot y^{-1} \pmod{998\,244\,353}$, where $x, y$ are integers and $y \not\equiv 0 \pmod{998\,244\,353}$. You need to output $x \cdot y^{-1} \pmod{998\,244\,353}$, where $y^{-1}$ is the modular multiplicative inverse of $y$.
Examples
Input 1
7 20 0 0 0 0 499122177 0 499122177 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output 1
990445569
Input 2
8 3 812138959 45623385 495509199 897977157 247249999 287689259 681189598 378052607 543965309 867598107 134549080 632982832 328959167 357361552 721347208 655511975 533423256 201648269 632527095 93857530 78231607 947693525 184253338 40189465 338389318 841013441
Output 2
517646448