题目描述

基于括号序列可以出许多有趣的简单算法题，一个合法括号序列的定义如下：

1. () 是合法的。
2. 如果括号序列 X 是合法的，那么括号序列 (X) 是合法的。
3. 如果括号序列 X 和 Y 都是合法的，那么括号序列 XY 是合法的

例如，括号序列 ()()(()) 是合法的，()))()(( 是不合法的。

定义一个生成括号序列的操作流程：

• 给定长度为 $n$ 的整数序列 $c_0, c_1, \ldots, c_{n-1}$，依次执行 $n$ 次操作构建括号序列。
• 初始时括号序列为空，第 $i+1$ 次操作时，若 $i$ 为偶数，则往当前括号序列末尾加人 $c_i$ 个左括号；否则就往当前括号序列末尾加 $c_i$ 个右括号。

例如，序列 3211 构建出来的括号序列为 ((())()。

注意，按照上述流程构建出来的括号序列 $\mathrm{S}$ 不一定是合法的，但是 $\mathrm{S}$ 的子串有可能是合法括号序列，请求出 $\mathrm{S}$ 的非空子串是合法括号序列的数量。

即求有多少个区间 $[l, r](1 \leq l \leq r \leq|S|)$， 使得 $S[l, r]$ 是合法括号序列。

输入格式

本题采用如下方式生成输入数据：

输入仅一行，8 个整数 $n, x, y, z, m_0, m_1, c_0, c_1$。

对于 $i>1, c_i=\left(c_{i-1} \times x+c_{i-2} \times y+z\right) \bmod M_i+1$，其中当 $i$ 为偶数时 $M_i=m_0$，当 $i$ 时奇数时 $M_i=m_1$。

整数序列 $c$ 的含义如题所述。

	vector<int> c(n);
	int x,y,z,m[2]; scanf("%d%d%d%d%d%d%d",&x,&y,&z,&m[0],&m[1],&c[0],&c[1]);
	for(int i=2;i<n;++i) c[i]=(1ll*c[i-1]*x+1ll*c[i-2]*y+z)%m[i%2]+1;

输出格式

一行一个整数表示 $\mathrm{S}$ 中合法的非空括号子串的数量。

10 686962104 149902149 5232363 10 4 7 3

15

附加样例

sample_brackets1.in
sample_brackets1.out

sample_brackets2.in
sample_brackets2.out

数据范围

$\begin{aligned} & 1 \leq n \leq 10^7, 0 \leq x, y, z \leq 10^9, 1 \leq c_0 \leq m_0 \leq 10^9, 1 \leq c_1 \leq m_1 \leq 10^9 \\ & \text { subtask } 1(8 p t s): n \leq 20, \max \left\{m_0, m_1\right\} \leq 500 \\ & \operatorname{subtask} 2(16 p t s): n \leq 5000, \max \left\{m_0, m_1\right\} \leq 4000 \\ & \text { subtask } 3(8 p t s): n \leq 20 \\ & \text { subtask } 4(16 p t s): n \leq 5000 \\ & \text { subtask } 5(8 p t s): n \leq 10^6, m_1=1 \\ & \text { subtask } 6(28 p t s): n \leq 10^6 \\ & \text { subtask } 7(16 p t s): \text { 无限制 }\end{aligned}$