Có ~n~ sinh viên đã tham gia một kỳ thi. Các sinh viên được đánh số từ Sinh viên ~1~, Sinh viên ~2~, ..., Sinh viên ~n~, và sinh viên thứ ~i~ được ~a_i~ điểm.

Sinh viên nào đạt dưới ~k~ điểm được coi là không đạt và không thể nhận được tín chỉ.

Hãy tìm số lượng sinh viên không đạt trong kỳ thi.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n, k(1 \le n,k \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n(1 \le a_i \le 10^5)~ ~-~ điểm số của các sinh viên.

Output

• Gồm một dòng duy nhất số lượng sinh viên không đạt trong kỳ thi.

Sample Input

4 50
80 60 40 0

Sample Output

2

Bạn đang có ~M~ xâu, xâu thứ ~i~ được gọi là ~s_i~, độ dài mỗi xâu không quá ~6~ và chỉ có các kí tự a, b.

Yêu cầu: Bạn hãy đếm số xâu ~T~ độ dài ~N~, chỉ chứa các kí tự a, b mà không chứa bất kì một sâu ~s_i(1 \le i \le M)~ nào.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~N,M(1 \le N \le 10^{18}, 1 \le M \le 126)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ là xâu ~s_i(1 \le |s_i| \le 6)~

Output

• Một dòng duy nhất, kết quả của đề bài khi chia lấy dư cho ~998244353~.

Sample Input

3 2
ab
bb

Sample Output

2

Subtask

• Có ~33\%~ số test thỏa mãn: ~1 \le N \le 20, 1 \le M \le 64~.
• Có ~67\%~ số test thỏa mãn: Như giới hạn đề bài.

Giải thích

• Các xâu thỏa mãn là: aaa, baa.

Tèo đang trong một cửa hàng, và Tèo có một ba lô có sức chứa tối đa là ~M~, Tèo bắt đầu đi shooping ...

Có ~N~ món đồ được đánh số từ ~1~ đến ~N~. Món đồ thứ ~i~ có trọng lượng là ~w_i~ và giá trị là ~v_i~.

Được biết sẽ có vài món đồ phụ thuộc vào nhau. Nếu ~d_i = j(i>j)~ tức nếu muốn mua món đồ thứ ~i~ thì phải mua món đồ thứ ~j~ trước, nếu ~j = 0~ thì món đồ này có thể mua bất kì lúc nào không phụ thuộc bởi các món đồ khác. Đảm bao mỗi món đồ chỉ phụ thuộc tối đa ~1~ món đồ khác, và các mối phụ thuộc này hợp lý, không xảy ra vòng lặp.

Vì Tèo không giỏi trong việc tính toán nên bạn hãy giúp Tèo tính toán chọn mua các đồ sao cho không quá sức chứa của ba lô mà mang lại giá trị lớn nhất.

Input

• Dòng đầu gồm ~2~ số nguyên ~N, M~ ~(1 \le N,M \le 6*10^4)~
• Dòng thứ hai hồm ~n~ số nguyên ~d_1, d_2, ... d_n(0 \le d_i < n)~.
• Dòng thứ ba hồm ~n~ số nguyên ~w_1, w_2, ... w_n(1 \le w_i \le 200)~.
• Dòng thứ tư hồm ~n~ số nguyên ~v_1, v_2, ... v_n(0 \le v_i \le 5000)~.

Output

• Gồm ~1~ dòng duy nhất là kết quả của bài toán, giá trị lớn nhất thu được.

Sample Input

5 3
0 0 1 2 0
1 1 1 1 1
2 2 1 2 3

Sample Output

7

Subtask

• ~1 \le N*M \le 6*10^7~
• Có ~22\%~ số test thỏa mãn: ~1 \le N \le 100, 1 \le M \le 12~.
• Có ~6\%~ số test thỏa mãn: ~1 \le N \le 200, 1 \le M \le 250, v_i = 1~.
• Có ~6\%~ số test thỏa mãn: ~1 \le N \le 200, 1 \le M \le 250, w_i = 1~.
• Có ~6\%~ số test thỏa mãn: ~1 \le N \le 200, 1 \le M \le 250~.
• Có ~20\%~ số test thỏa mãn: ~1 \le N \le 400, 1 \le M \le 500~.
• Có ~20\%~ số test thỏa mãn: ~1 \le N \le 7500, 1 \le M \le 8000~.
• Có ~10\%~ số test thỏa mãn: ~1 \le N \le 50000, 1 \le M \le 1200~.
• Có ~10\%~ số test thỏa mãn: ~1 \le N \le 1000, 1 \le M \le 60000~.

Có một đồ thị vô hướng với ~n~ đỉnh và ~m~ cạnh, mỗi đỉnh được đánh số từ ~1~ đến ~n~. Bạn cần giải ~q~ truy vấn, truy vấn thứ ~i~ bạn được cho một số ~k_i~ tức trong truy vấn đó bạn chỉ có ~k_i~ loại màu.

Yêu cầu: Với mỗi truy vấn tô màu mỗi đỉnh của đồ thị trên sao cho hai đỉnh có cạnh nối không cùng màu. Tính số cách tô màu hợp lệ, chia lấy dư cho ~10^9+7~

Input

• Dòng đầu tiên gồm ba số nguyên ~n, m, q(1 \le n \le 10^5, 0 \le m \le min(10^5,n*(n-1)/2),1 \le q \le 1000)~ ~-~ lần lượt là thị số lượng đỉnh, số lượng cạnh và số lượng truy vấn.
• ~m~ dòng tiếp theo mỗi dòng gồm hai số nguyên ~u_i, v_i~ - có một cạnh nối giữa chúng. Đảm bảo không có cạnh trùng lặp.
• ~q~ dòng tiếp theo mỗi dòng gồm một số nguyên ~k_i(1 \le k_i \le 10^9)~ ~-~ trong truy vấn đó có ~k_i~ loại màu.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~ chia lấy dư cho ~10^9+7~.

Sample Input

5 4 4
1 2
2 3
3 4
4 5
2
3
4
5

Sample Output

2
48
324
1280

Subtask

• Có ~18\%~ số test thỏa mãn: ~1 \le n,k \le 8, 1 \le q \le 50~.
• Có ~26\%~ số test thỏa mãn: ~1 \le n \le 15~.
• Có ~20\%~ số test thỏa mãn: ~1 \le m \le 24~.
• Có ~36\%~ số test thỏa mãn: Mỗi đỉnh có đúng hai cạnh nối với nó.

Hint

• Brute đi nào