Chords

Problem Description

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 minor triad includes all chords of the format {$x, x+3, x+7$}. Similarly, the chord class dominant seventh 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$.

Input

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$.

Output

For each test case, output the answer modulo $1062125569$ in a single line.

Sample Input

1
5 2
3 4 2 5 1
0 2

Sample Output

28

Source

2023“钉耙编程”中国大学生算法设计超级联赛（8）