题目描述
Imagine a mystical forest where a magic piano with $n$ keys resides. Each key of this piano represents a note, denoted by positive integers from $1$ through $n$. In musical terms, a chord is defined as a set of notes played together in harmony. The type or class of a chord is categorized based on the difference between its root note (the lowest note) and the other notes in the chord.
For instance, the chord class known as [i]minor triad[/i] includes all chords of the format {$x, x+3, x+7$}. Similarly, the chord class [i]dominant seventh[/i] includes all chords that follow the pattern {$x, x+4, x+7, x+10$}.
For each key $x$ on the piano (which produces the note $x$), you can play it with $a_x$ different strengths, each of which produces a unique sound. As a result, you can produce $a_x$ distinct sounds from that note. More interestingly, for a minor triad with root note $x$ as an example, you can produce $a_x \times a_{x+3} \times a_{x+7}$ unique sounds.
Now, consider a given chord class represented by {$x + b_1, x+b_2, ..., x+{b_m}$}. Your task is to calculate the total number of different sounds you can produce when you are free to choose any root note $x$.
For instance, the chord class known as [i]minor triad[/i] includes all chords of the format {$x, x+3, x+7$}. Similarly, the chord class [i]dominant seventh[/i] includes all chords that follow the pattern {$x, x+4, x+7, x+10$}.
For each key $x$ on the piano (which produces the note $x$), you can play it with $a_x$ different strengths, each of which produces a unique sound. As a result, you can produce $a_x$ distinct sounds from that note. More interestingly, for a minor triad with root note $x$ as an example, you can produce $a_x \times a_{x+3} \times a_{x+7}$ unique sounds.
Now, consider a given chord class represented by {$x + b_1, x+b_2, ..., x+{b_m}$}. Your task is to calculate the total number of different sounds you can produce when you are free to choose any root note $x$.
输入
The first line of the input contains a single integer $T$ ($1 \leq T \leq 10^3$), denoting the number of test cases.
The first line of each test case contains two integers $n,m$ ($1 \leq m \leq n \leq 5\times 10^5$) separated by space, denoting the number of keys in the piano and the number of notes in the given chord class.
The second line of each test case contains $n$ positive integers $a_1, \ldots, a_n$ ($0 < a_x < 1062125569$), each representing the number of different strengths that can be applied to the corresponding key $x$.
The third line of each test case contains $m$ ascending integers $b_1, \ldots, b_m$ ($0 = b_1 < b_2 < \ldots < b_m < n$), denoting the given chord class.
It is guaranteed that the sum of $n$ over all test cases will not exceed $10 ^ 6$.
The first line of each test case contains two integers $n,m$ ($1 \leq m \leq n \leq 5\times 10^5$) separated by space, denoting the number of keys in the piano and the number of notes in the given chord class.
The second line of each test case contains $n$ positive integers $a_1, \ldots, a_n$ ($0 < a_x < 1062125569$), each representing the number of different strengths that can be applied to the corresponding key $x$.
The third line of each test case contains $m$ ascending integers $b_1, \ldots, b_m$ ($0 = b_1 < b_2 < \ldots < b_m < n$), denoting the given chord class.
It is guaranteed that the sum of $n$ over all test cases will not exceed $10 ^ 6$.
输出
For each test case, output the answer modulo $1062125569$ in a single line.
样例输入 Copy
1
5 2
3 4 2 5 1
0 2
样例输出 Copy
28