Huy và Châu trong công cuộc tìm lại cảm hứng đã quyết định đào sâu về toán học, đặc biệt là phần số học. Để tìm kiếm tài liệu, hai cậu quyết định đi tới tuyển Tin Ams, và vô tình thấy được một bài toán khó như sau được viết trên bảng:

Cho mảng ~a~ gồm ~n~ phần tử nguyên dương và một số nguyên dương ~k~.

Ta đều biết các số nguyên dương đều có thể phân tích dưới dạng thừa số nguyên tố, vậy nên đỡ mất thời gian phân tích gây tổn hại máy chấm, bạn sẽ nhận được số nguyên dương ~k~ dưới dạng phân tích thừa số nguyên tố của nó. Nói cách khác, bạn sẽ nhận được hai dãy nguyên dương ~p~ và ~x~ gồm ~m~ phần tử, thỏa mãn ~p~ gồm các số nguyên tố phân biệt. Lúc này ~k = p_1^{x_1} \times p_2^{x_2} \times p_3^{x_3} \times ... \times p_m^{x_m}~.

Giả sử ~S~ là một dãy con của dãy ~a~ (bao gồm cả dãy rỗng), ta có định nghĩa sau:

• Gọi ~LCM(S)~ là bội chung nhỏ nhất của mọi phần tử thuộc ~S~. Đối với ~S = \emptyset~, giá trị này được coi là ~1~.
• Gọi ~G(S)~ là trọng số của dãy con ~S~, giá trị ~G(S) = x~ với ~x~ là số nguyên dương nhỏ nhất thỏa mãn: ~k | LCM(S) \times x~, hay ~LCM(S) \times x~ chia hết cho ~k~.

Hãy tính tổng trọng số của các dãy con ~S~ thoả mãn ~G(S) = 1~, hay nói cách khác đếm số dãy con sao cho bội chung nhỏ nhất của nó chia hết cho ~k~.

Sau khi đọc xong, hai cậu mới biết rằng hóa ra đây là một đề bài được dự định sẽ cho vào ~AMSOI~ ~Round~ ~4~. Vốn đều là những người có ước mơ được thi ~VMO~ cháy bỏng, hai cậu đã nhanh chóng tìm ra lời giải của bài toán, thậm chí còn có thể giải một yêu cầu tổng quát hơn như sau:

Thay vì chỉ tính các dãy con ~S~ có ~G(S) = 1~, nhiệm vụ của bạn là hãy tính tổng trọng số của toàn bộ dãy con trong ~S~.

Tuy nhiên, Huy lại muốn đưa nó vào đề bài chính thức, Châu lại bảo như vậy là quá khó với các bạn học sinh. Vậy nên, hai cậu quyết định thuyết phục thầy ... đưa cả hai dạng yêu cầu này vào bài. Và đó là lý do tại sao bạn lại đọc được đề của nó vào ngày hôm nay.

Để hiện thực hóa thỉnh cầu của học trò, ~mrtee~ sẽ cho bạn một tham số ~t~.

Với ~t = 1~, bạn hãy in ra kết quả của yêu cầu thứ nhất:

Hãy tính tổng trọng số của các dãy con ~S~ thoả mãn ~G(S) = 1~, hay nói cách khác đếm số dãy con sao cho bội chung nhỏ nhất của nó chia hết cho ~k~.

Với ~t = 2~, bạn hãy in ra kết quả của yêu cầu thứ hai:

Thay vì chỉ tính các dãy con ~S~ có ~G(S) = 1~, nhiệm vụ của bạn là hãy tính tổng trọng số của toàn bộ dãy con trong ~S~.

Với cả hai yêu cầu, tổng bạn cần tính đều có giá trị rất lớn, vậy nên hãy in nó ra sau khi lấy phần dư cho ~10^9+7~.

Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu như ta có thể bỏ bớt một vài phần tử của ~a~ và giữ nguyên thứ tự của các phần tử còn lại để thu được dãy ~b~.

Hai dãy con được gọi là khác nhau nếu tồn tại một vị trí ~i~ sao cho phần tử thứ ~i~ của dãy ~a~ được bỏ đi để tạo ra dãy con thứ nhất, nhưng không được bỏ đi để tạo ra dãy con thứ hai.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n,m,t~ (~1 \le n \le 10^5; 1 \le m \le 16; 1 \le t \le 2~).
• Dòng thứ hai gồm ~m~ số nguyên dương miêu tả dãy ~p~, dữ liệu đảm bảo rằng đây đều là các số nguyên tố và chúng đôi một khác nhau (~2 \le p_i \le 10^6~).
• Dòng thứ hai gồm ~m~ số nguyên dương miêu tả dãy ~x~ ~(1 \le \sum_{i=1}^{m} x_i \le 20)~.
• Dòng cuối cùng gồm ~n~ số nguyên dương miêu tả dãy nguyên dương ~a~ (~1 \le a_i \le 10^{9}~).

Output:

• Với ~t = 1~, hãy in ra kết quả của yêu cầu thứ nhất, ngược lại với ~t = 2~ in ra kết quả của yêu cầu thứ hai. Vì kết quả có thể rất lớn nên hãy in nó ra sau khi lấy phần dư với ~10^9+7~.

Subtask:

• Subtask ~1~ (~10\%~ số điểm): ~t = 1; n \le 20; a_i \le 15; k \le 10^9~.
• Subtask ~2~ (~15\%~ số điểm): ~t = 1; n \le 50; a_i \le 15; k \le 10^9~.
• Subtask ~3~ (~20\%~ số điểm): ~t = 2; m \le 6; x_i = 1 \forall i \in [1,m]~.
• Subtask ~4~ (~25\%~ số điểm): ~t = 2; x_i = 1 \forall i \in [1,m]~.
• Subtask ~5~ (~15\%~ số điểm): ~t = 1~.
• Subtask ~6~ (~15\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3 2 1
2 3
1 1
4 9 5

Sample Output 1

2

Sample Input 2

5 2 1
3 2
2 1
4 24 17 18 3

Sample Output 2

16

Sample Input 3

3 2 2
2 3
1 1
4 9 5

Sample Output 3

24

Sample Input 4

7 2 2
3 2
2 2
4 24 17 18 3 9 6

Sample Output 4

332

Explanation

Trong ví dụ thứ nhất, có hai dãy con ~S~ có ~G(S) = 1~ là dãy ~\{1;2\}~ và dãy ~\{1;2;3\}~.

Trong ví dụ thứ hai, có ~16~ dãy thỏa mãn chia hết cho ~k = 18~.

Ở ví dụ thứ ba với ~t = 2~ ta cần trả lời câu hỏi dạng thứ hai. Do ~k = 6~, ta sẽ xét các dãy con sau:

• ~\{\emptyset\}~: Dãy rỗng có ~LCM(\emptyset) = 1~, như vậy ~G(S) = 6~
• Ba dãy con độ dài ~1~: ~\{1\}~; ~\{2\}~; ~\{3\}~ lần lượt có ~G(S)~ là ~3;2;6~.
• Ba dãy con có độ dài ~2~: ~\{1;2\}~; ~\{2;3\}~; ~\{1;3\}~ lần lượt có ~G(S)~ là ~1;2;6~.
• Dãy con ~\{1;2;3\}~ có ~G(S) = 1~.
• Tổng lại ta thu được đáp án cho toàn bộ dãy con là ~24~.