题目背景

除了丰富的迷宫系统之外,TODR的弹幕系统也富有趣味,不仅有多种华丽的特效,还有如咲夜的连发小刀,The World等特殊的攻击.

不仅自机如此,敌人也有自己独特的攻击方式,比如下图就是绵月丰姬的"净化之风"攻击模式

题目描述

通过了不可思议的迷宫后,你一路顺利地过关斩将来到了最后一层,却遭遇了前所未有的强敌——纯狐

所幸的是,纯狐的弹幕不像绀珠转的强度一样大,房间的地形也比较特殊,可以为你所用.

形式化的来说,每一回合你和纯狐的行动模式如下:

1. 你可以将房间当成一张正方形网格图,左下角坐标为$(0,0)$,右上角的坐标为$(n,n)$,房间的有效位置为这$(n+1)*(n+1)$个格点,在一回合开始的时候,你会被随机传送到房间的任意一个有效位置

2. 之后,纯狐会随机出现在房间中的某个有效位置,当然,她不会和你出现在同一位置

3. 纯狐会发射纯粹的自机狙,也就是向你的方向发射一片弹幕,如果这片弹幕在飞行过程中经过了某个不是纯狐和自机所在的格点,则格点上的弹幕结界会被触发,将其传送到亚空间,如果这片弹幕顺利到达你所在的格点,那么你会受到一些伤害

4. 由于时间狂暴,纯狐在第$t$回合的弹幕伤害可以计算为$at^{2}+bt+c$

5. 回合结束,开始下一回合

经过粗略估计,你认为和纯狐的弹幕战会持续$k$回合,那么,为了稳妥起见,你想要算出自机受到的总期望伤害

答案可能很大也可能丢精度,所以对$19260817$取模就可以了

输入格式

一行五个整数$n,a,b,c,k$,意义与题目描述保持一致

输出格式

一行一个整数,表示期望受到总伤害的值

1 1 2 1 1

3

1 1 2 1 5

9630476

提示

样例$1$解释:

手画一个网格图,不难发现纯狐能打到你的情况有$12$种(先放自机再放纯狐即可得到)

所以第一发弹幕的伤害为$1*1*1+2*1+1=4$,期望伤害为$4*\frac{12}{16}=3$

只有一回合,所以答案为$3$

数据范围: