Hôm nay, nqson đang nghiên cứu những phép tính về giai thừa để giải các bài tập trên ltol. Giai thừa của một số tự nhiên $n$ được ký kiệu là $n!=1.2.3....n$, với quy ước $0!=1$. nqson có một dãy số tự nhiên và một số $x$ không lớn hơn số lớn nhất trong dãy, cậu muốn tính giai thừa của từng số trong dãy, nhân hết tất cả lại rồi chia cho $x!$ ra được kết quả cần tìm.

Nhưng hôm nay là giáng sinh, bài này lại khó quá nên nqson cần nhờ các bạn giải để cậu có thể được đi chơi. Các bạn hãy giúp nqson nhé.

Đầu vào

Dòng đầu tiên chứa số tự nhiên $n$ $(1\le n\le {10}^6)$, số phần tử trong dãy số.

Dòng tiếp theo chứa $n$ số tự nhiên $a_1,a_2,a_3,...,a_n$ $(1\le a_i\le {10}^6)$, các phần tử của dãy số.

Dòng cuối cùng chứa số tự nhiên $x$ $(1\le x\le max(a_i))$.

Đầu ra

Một số tự nhiên duy nhất là kết quả của bài toán, do số có thể rất lớn nên bạn hãy lấy số dư khi chia cho $2\ast {10}^9+14$.

Subtask

$10\mathrm{\%}$ số test có $n\le 10;a[i]\le 10$

$20\mathrm{\%}$ số test có $n\le 1000;a[i]\le 1000$

$10\mathrm{\%}$ số test có $n\le {10}^6;a[i]\le {10}^6;x=1$

$60\mathrm{\%}$ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Đầu vào:

3
1 2 5
4

Đầu ra:

10

Giải thích: $1!.2!.5!/4!=10$.