Đàn cá mập và những bông hoa

Có $n$ con cá mập ngồi quanh một chiếc bàn tròn. Với mọi $i$ từ $1$ đến $n-1$, cá mập $i$ và cá mập $i+1$ là hàng xóm của nhau; ngoài ra cá mập $n$ và cá mập $1$ cũng là hàng xóm.

Cá mập thứ $i$ sẽ trồng được $s_i$ bông hoa, trong đó $s_i$ là một số nguyên được chọn ngẫu nhiên với xác suất như nhau trong đoạn $[l_i,r_i]$. Các giá trị $s_1,s_2,\dots ,s_n$ được chọn độc lập với nhau.

Ông chủ có một số nguyên tố yêu thích là $p$. Xét từng cặp cá mập hàng xóm $i$ và $j$: nếu tích $s_i·s_j$ chia hết cho $p$ thì ông chủ thưởng $1000$ đô la cho mỗi con trong cặp đó, tức là cặp này làm tổng tiền thưởng tăng thêm $2000$ đô la. Một con cá mập có thể được thưởng nhiều lần, mỗi lần ứng với một cặp hàng xóm khác nhau mà nó tham gia.

Hãy tính kỳ vọng của tổng số tiền mà cả đàn cá mập nhận được.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $p$: số lượng cá mập và số nguyên tố yêu thích của ông chủ.
• Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên $l_i$ và $r_i$: đoạn giá trị mà $s_i$ có thể nhận.

Dữ liệu ra

In ra một số thực duy nhất là kỳ vọng của tổng số tiền thưởng. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối so với đáp án đúng không vượt quá ${10}^{-6}$.

Ràng buộc

• $3\le n\le {10}^5$
• $2\le p\le {10}^9$, $p$ là số nguyên tố
• $1\le l_i\le r_i\le {10}^9$

Ví dụ