Expected Damage in the Purefox Bullet Barrage

You are trapped in a final level of a mysterious labyrinth facing an unprecedented enemy — Purefox. Although Purefox's barrage is not as intense as that of Kanjutan, the room's terrain (a square grid) can be used to your advantage.

Formally, the battle proceeds in k rounds. In each round:

1. You are randomly teleported to one of the grid points in a square room whose bottom‐left corner is at (0, 0) and top‐right at (n, n). There are a total of (n+1)×(n+1) valid positions.
2. Then, Purefox appears uniformly at random in one of the valid grid points (different from your current position).
3. Purefox fires a bullet barrage aimed at your position. However, as the bullet travels, if it passes through any grid point that is neither the shooter’s nor your own, the magical barrier on that grid point will be triggered and the bullet will be diverted to another dimension. Hence, you will only be hit if the bullet’s straight line from Purefox to you does not pass through any other grid point.
4. It can be shown that the bullet will hit you if and only if the two positions are "visible" from each other; that is, if the vector difference (dx, dy) between the two points is primitive (i.e. \(\gcd(|dx|,|dy|)=1\)).
5. In the t-th round, if you get hit, you suffer damage equal to \(at^2+bt+c\).
6. Then the round ends and the next round starts.

You estimate that the battle will last for k rounds. Since both players’ positions are uniformly random (with the enemy never appearing at your current position), the probability that you are hit in any round is:

[ P=\frac{\text{# of pairs of positions (P,E) with } \gcd(|dx|,|dy|)=1}{(n+1)^2\Bigl((n+1)^2-1\Bigr)} ]

Your task is to compute the expected total damage over k rounds modulo 19260817. In other words, if \(S=\sum_{t=1}^{k}(at^2+bt+c)\) then you need to compute

[ \text{Answer} = P \times S ;\bmod; 19260817. ]

Note: Because the answer may be huge and involve division, perform all operations under modulo arithmetic (using modular inverses, etc.).

inputFormat

The input consists of a single line containing five integers separated by spaces:

• a, b, c (\(0\le a,b,c \le 10^9\)) — the coefficients for the damage function.
• An integer n (\(1 \le n \le 10^5\)) representing that the grid has coordinates from \(0\) to \(n\) (inclusive) in both directions. Thus, there are \((n+1)^2\) valid positions.
• An integer k (\(1 \le k \le 10^9\)) representing the number of rounds.

The positions for you and Purefox are chosen uniformly at random as described in the statement.

outputFormat

Output a single integer — the expected total damage you will incur modulo 19260817.

sample

1 1 1 1 1

3