纯粹的弹幕地狱

除了丰富的迷宫系统之外,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$ 数据范围: