题目描述

给你一个正整数 $n$，有数列 $1,2,3,...,n$。

分别求相邻两项中左边一项的 $a$ 倍与右边一项的 $b$ 倍的和再加上 $c$，得到一个有 $n-1$ 项的新数列：

$1\times a+2\times b+c,2\times a+3\times b +c,...,(n-1)\times a+n\times b+c$。

对这个新数列重复上述操作得到若干数列，最后的数列只有一项，求最后这个项对 $p$ 取模的值。

输入格式

一行，五个非负整数 $n,a,b,c,p$。

输出格式

一个整数，表示答案对 $p$ 取模的值。

1 1 1 1 1000000007

1

4 2 3 1 1000000007

381

23 19 17 0 1000000007

323147645

233 233 233 233 1000000000

770969703

提示

【样例解释】

样例 2：

各数列分别为：

1 2 3 4
9 14 19
61 86
381

【数据范围】

• 对于 $80 \%$ 的数据，满足 $p$ 为质数。

• 对于 $100 \%$ 的数据，满足 $1\le n\le 10^{18}$，$1\le p \le 10^{14}$，$1 \le a,b\le 10^9$，$0\le c \le 10^9$。