暂无测试数据。

题目背景

$\color{brown}{\sf 2024yuhongyi}$ 遇到了一个问题）~~没有人会遇到这种问题。~~

他不会，所以想请你帮忙和他一起哈哈哈。

题目描述

给定一个长度为 $n$ 的**数列** $a$。

每次询问给定一个**区间** $[l,r]$，和一个**质数** $p$。

请你求出：

$$\prod _{i=l}^r[\frac{(\sum_{j=l}^ia_jp)!}{\prod_{j=l}^ip^{a_j}(\sum_{j=l}^ia_j)!}\bmod p]\bmod (10^9+7)$$

输入格式

第一行，两个数，代表 $n$ 和 $q$。

接下来 $q$ 行，每行三个数，对应每次询问的 l r p。

输出格式

共 $m$ 行，每行一个数，代表每次询问的答案。

样例 #1

样例输入 #1

5 5
1 5 3 5 2
1 5 2
2 4 3
3 5 11
1 1 2
1 5 10007

样例输出 #1

1
4
10
1
100120036

样例 #2

样例输入 #2

50 10
534 6534 324 789 79 789 798 7984 43 2 534 6534 324 789 79 789 798 7984 43 2 534 6534 324 789 79 789 798 7984 43 2 534 6534 324 789 79 789 798 7984 43 2 534 6534 324 789 79 789 798 7984 43 2
2 34 2
5 6 11
1 49 17
2 50 97
45 48 7
3 3 2
1 50 10007
30 40 10007
1 10 10007
5 50 5

样例输出 #2

1
10
496641140
291552291
6
1
356715574
538473149
538473149
383381198

提示

数据范围：

因为这是，所以请你忽略以上分值。

对所有数据都有：

$1 \le n \le 10^6,1 \le q \le 2 \times 10^5,1 \le a_i \le 10^9,1 \le l \le r \le n,2 \le p \le 10^6$。

其中 $p$ 总是质数。