Problem Background

In addition to the rich maze system, TODR's bullet system is also quite interesting, featuring various splendid effects, as well as special attacks like Sakuya's rapid knives and The World.

Not only are the player's attacks unique, but the enemies also have their own distinctive attack patterns. For example, the image below shows the "Purifying Wind" attack mode of Watatsuki no Toyohime.

Problem Description

After passing through the incredible maze, you have successfully made your way to the final level, only to encounter an unprecedentedly powerful enemy—Junko.

Fortunately, Junko's bullets are not as intense as those in the Azure Orb, and the room's terrain is quite special and can be used to your advantage.

Formally, each round follows this pattern:

1. You can consider the room as a square grid, with the bottom-left coordinate being $(0,0)$ and the top-right coordinate being $(n,n)$. The valid positions in the room are these $(n+1) \times (n+1)$ grid points. At the beginning of each round, you are randomly teleported to any valid position in the room.

2. Then, Junko will randomly appear at a valid position in the room, of course, she will not appear at the same position as you.

3. Junko will fire a pure homing shot, which means she will shoot a barrage towards your direction. If this barrage passes through a grid point that is neither Junko nor the player, the bullet barrier at that point will be triggered, teleporting it to subspace. If the barrage reaches your position, you will take some damage.

4. Due to time frenzy, the damage of Junko's barrage in the $t$-th round can be calculated as $at^2 + bt + c$.

5. The round ends, and the next round begins.

After a rough estimate, you believe that the bullet battle with Junko will last for $k$ rounds. Therefore, to be on the safe side, you want to calculate the expected total damage taken by the player.

The answer may be very large or lose precision, so take it modulo $19260817$.

Input Format

A line containing five integers $n, a, b, c, k$, with meanings consistent with the problem description.

Output Format

A line containing one integer, representing the expected total damage taken.

Sample Input and Output

Sample Input #1

1 1 2 1 1

Sample Output #1

3

Sample Input #2

1 1 2 1 5

Sample Output #2

9630476

Notes

Sample $1$ Explanation:

By manually drawing a grid, it is不难发现 that there are $12$ possible situations where Junko can hit you (placing the player first and then Junko will give you this result).

So the damage of the first barrage is $1 \times 1 \times 1 + 2 \times 1 + 1 = 4$, and the expected damage is $4 \times \frac{12}{16} = 3$.

Since there is only one round, the answer is $3$.

Data Range:

见题面 Input 部分

见题面 Output 部分