Do sự phổ biến gần đây của Deep learning các quốc gia mới đang bắt đầu trông giống như mạng thần kinh. Đó là, các nước đang được xây dựng với nhiều lớp, mỗi lớp có thể có nhiều thành phố. Mỗi nước cũng có một điểm đầu và một điểm cuối.

Mỗi nước có chính xác L lớp, mỗi lớp có N thành phố. Quan sát hai lớp kề nhau L1 và L2. Mỗi thành phố thuộc lớp L1 được nối với một thành phố thuộc lớp L2 với một chi phí di chuyển là c_ij  với mọi i, j thuộc {1, 2, ..., N} và mỗi cặp lớp lân cận có cùng chi phí ở giữa các thành phố của chúng với nhau như bất kỳ cặp nào khác. Chi phí di chuyển của mọi thành phố thuộc lớp L1 đến một thành phố thuộc lớp L2 là giống nhau, nghĩa là c_ij là như nhau với mọi i thuộc {1, 2, ..., N} và j cố định.

Yêu cầu: Tìm số lượng đường đi để một người bắt đầu đi tại điểm đầu và kết thúc tại điểm cuối sao cho chi phí đi lại của người đó có thể chia hết cho số M cho trước.

Dữ liệu

Dòng đầu chứa số N (1 ≤ N ≤ 10⁶), L (2 ≤ L ≤ 10⁵) và M (2 ≤ M ≤ 100), là số lượng thành phố trong từng lớp, số lượng lớp và số M là chi phí của đường đi cần phải chia hết.

Dòng thứ hai, ba, bốn chứa N số nguyên (mỗi số biểu thị chi phí di chuyển cost mà 0 ≤ cost ≤ M) lần lượt là chi phí tới lớp đầu tiên, chi phí giữa hai lớp kề nhau như mô tả ở trên và chi phí từ lớp cuối cùng tới điểm kết thúc.

Kết quả

Chứa một số nguyên là số lượng đường đi mà tổng chi phí chia hết cho M, modulo 10⁹ + 7.