You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给你一个正整数 $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

---

【数据范围】

测试点编号	$n\le$	$p\le$	$a,b\le$	$c\le$
$1\sim 4$	$10^3$	$10^9+7$	$10$
$5\sim 8$	$10^6$	$10^{14}$	$10^3$
$9,10$	$10^9$	$10^9+7$	$1$	$0$
$11,12$				$10^9$
$13,14$	$10^{18}$
$15,16$			$10^9$
$17 \sim 20$		$10^{14}$

• 对于 $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$。