题目描述

给定一个长度为 $N$ 的序列 $A$，初始时 $A_i = i$（即 $A_1=1, A_2=2, \dots, A_N=N$）。

接下来有 $Q$ 次操作，分为以下两种：

1. 区间线性变换：给定 $l, r, a, b$，对于所有 $x \in [l, r]$，将 $A_x$ 更新为 $a \cdot x + b$。注意这里的 $x$ 是下标，不是当前的值。
2. 区间查询：给定 $l, r$，询问当前序列中 $\sum_{i=l}^{r} A_i^2$ 的值。

由于答案可能很大，请对 $10^9 + 7$ 取模后输出。

输入格式

第一行包含两个整数 $N, Q$，表示序列长度和操作次数。 接下来 $Q$ 行，每行描述一个操作：

• 若第一个数为 1，则该行包含 5 个整数 $l, r, a, b$，表示执行区间线性变换。
• 若第一个数为 2，则该行包含 3 个整数 $l, r$，表示执行区间查询。

数据范围与提示

对于 100% 的数据：

• $1 \le N, Q \le 10^5$
• $1 \le l \le r \le N$
• $0 \le a, b < 10^9 + 7$

提示： 直接维护每个位置的值会导致超时。考虑使用线段树，并在节点上维护该区间内所有元素的平方和、一次方和以及下标的某些统计量。当施加线性变换 $A_x = ax+b$ 时，新的平方和可以通过旧的统计量和下标的统计量推导出来。注意懒标记的合并规则。