Little C is a lucky player of Hollow Knight: Silksong. In the game, the player takes on the role of the deadly hunter "Hornet," stepping into a kingdom ruled by silk and song. Captured in a strange world, she faces powerful enemies and solves ancient mysteries on a deadly pilgrimage to reach the pinnacle of the kingdom. As a veteran Hollow Knight player, Little C has been enjoying the game day and night since its release. However, perhaps due to being out of practice or the increased difficulty of this installment, she finds herself dying frequently, so Little C decides to conduct an in-depth study of the game's difficulty.

The core currency system in the game is "Geo." Most items require Geo to purchase. Unfortunately, all Geo is lost upon death and cannot be recovered. However, the game provides a friendly "Geo Cache" mechanism—players can exchange a certain amount of Geo for a Geo Cache at a merchant. Geo Caches do not disappear upon death and persist after the player respawns. Specifically, if the player currently has at least $a$ Geo, they can consume $a$ Geo to exchange for one Geo Cache. A player can exchange any number of Geo Caches at a merchant, provided they meet the requirements. Additionally, at any time, the player can choose to dismantle a Geo Cache. Dismantling one Geo Cache increases the current amount of Geo by $b$ ($b \le a$), and the Geo Cache disappears.

The player's health in the game is measured in "Masks." At full health, the player has $c$ masks. When the number of masks reaches 0, the player dies, immediately returns to the nearest bench (respawn point), and is restored to full health. Health can only be recovered at benches. There are $m$ different types of enemies in the game. When facing an enemy of type $i$, Little C's combat outcome is characterized by a lower triangular matrix $P_i$: $P_{i,x,y}$ ($1 \le x \le c, 0 \le y \le x$) represents the probability that Little C has $x$ masks before fighting an enemy of type $i$ and $y$ masks after the fight. Specifically, $y=0$ represents that Little C dies after the fight. If Little C does not die after the fight, it means she has killed the enemy and will receive $w_i$ Geo.

To simplify the model, Little C abstracts the game into a linear design: there are $n$ levels in total, and she must pass them in increasing order of level number. Each level consists of three parts: a bench, enemies, and a merchant. At the start of a level, the player first passes the bench and restores health to full. Then, the player must face several enemies in sequence. If Little C dies while challenging an enemy, she will return to the bench of that level according to the rules above and restart the challenge for all enemies (previously defeated enemies in that level are reset to their initial state). If Little C successfully kills all enemies in the level, she can proceed to the merchant to synthesize Geo Caches or purchase items, and then enter the next level.

Little C knows that her current skill level is not great, so except for the merchant at the $n$-th level, every time she reaches a merchant, she will exchange as much of her current Geo as possible for Geo Caches, until the amount of Geo she holds is less than $a$.

Little C considers reaching the merchant at the $n$-th level as clearing the game, and she will dismantle all previously exchanged Geo Caches at the merchant of the $n$-th level. She wants to know, under these model assumptions, what is the expected number of Geo she possesses when she clears the game? The answer should be taken modulo 998244353.

Note: Some mechanisms described in the problem statement differ slightly from the actual game mechanics; please follow the descriptions in the problem statement.

Input

The first line contains five integers $n, m, a, b, c$ ($1 \le n, m, a, b \le 10^3, 1 \le c \le 10$), representing the number of levels, the number of enemy types, the amount of Geo required to exchange for one Geo Cache, the amount of Geo obtained by dismantling one Geo Cache, and the number of masks the player has at full health.

The second line contains $m$ integers $w_1, w_2, \dots, w_m$ ($1 \le w \le 10^6$), where $w_i$ represents the amount of Geo obtained by killing an enemy of type $i$.

Next, $m$ matrices are input, each occupying $c$ lines, where the $x$-th line contains $x+1$ integers. The $y$-th number in the $x$-th line of the $i$-th matrix is $p_{i,x,y-1}$ ($1 \le p_{i,x,y-1} \le 10^6$). Let $sum_{i,x} = \sum_{0 \le y \le x} p_{i,x,y}$, then the probability lower triangular matrix for the corresponding $i$-th enemy is calculated as $P_{i,x,y} = \frac{p_{i,x,y}}{sum_{i,x}}$ ($1 \le x \le c, 0 \le y \le x$).

The next $n$ lines each describe the information of a level: The beginning of each line is an integer $t_i$ ($1 \le t_i \le 100$), representing the total number of waves of enemies in this level. Next are $2t_i$ integers $ty_{i,1}, num_{i,1}, ty_{i,2}, num_{i,2}, \dots, ty_{i,t_i}, num_{i,t_i}$ ($1 \le ty_{i,j} \le m, 1 \le num_{i,j} \le 10^9$), representing that the level $i$ has a total of $\sum_{1 \le j \le t_i} num_{i,j}$ enemies, which are: $num_{i,1}$ enemies of type $ty_{i,1}$, $num_{i,2}$ enemies of type $ty_{i,2}$, and so on. Note that the player will challenge these enemies in sequence, facing only one enemy at a time.

Output

Output a single integer representing the expected number of Geo Little C possesses when clearing the game.

Examples

Input 1

3 2 5 3 1
3 2
1 2
1 1
2 1 1 2 1
1 2 3
1 1 3

Output 1

850356316

Note

In the example, there are 3 levels and 2 types of enemies. Every 5 Geo can be exchanged for one Geo Cache, and each Geo Cache can be dismantled for 3 Geo. The player has only 1 mask at full health.

For the first type of enemy, the player has a $1/3$ probability of being defeated (becoming 0 masks) and a $2/3$ probability of winning. Defeating one first-type enemy yields 3 Geo.

For the second type of enemy, the player has a $1/2$ probability of being defeated and a $1/2$ probability of winning. Defeating one second-type enemy yields 2 Geo.

The first level consists of one first-type enemy followed by one second-type enemy. After clearing the first level, Little C gains a total of $3+2=5$ Geo. Since 5 Geo is exactly enough to exchange for one Geo Cache, Little C will exchange for one Geo Cache after the first level, leaving her with 0 Geo. The second level consists of three second-type enemies. After clearing the second level, Little C gains a total of $2+2+2=6$ Geo. She will exchange for one Geo Cache after the second level, leaving her with 1 Geo.

The third level consists of three first-type enemies. If Little C clears the third level on her first attempt, the number of Geo she holds is (the 1 remaining from before) $1+3+3+3=10$ Geo, with a probability of $(2/3)^3 = 8/27$. Otherwise, if Little C dies in the third level, she loses all the Geo she is holding, and after several respawns, when she clears the third level, the number of Geo she holds is $3+3+3=9$ Geo, with a probability of $1 - 8/27 = 19/27$.

Adding the two previously accumulated Geo Caches, the expected number of Geo Little C finally holds is: $3 + 3 + (10 \times 8/27 + 9 \times 19/27) = 15 + 8/27 \equiv 850356316 \pmod{998244353}$.

Figure 1. The deadly hunter Hornet in Hollow Knight: Silksong