Định luật chữ số đầu

Định luật Benford phát biểu rằng trong nhiều bộ số lấy từ thực tế, các số có chữ số đầu tiên (chữ số có nghĩa lớn nhất) bằng $1$ xuất hiện nhiều hơn hẳn so với các chữ số khác. Ta sẽ kiểm chứng ý tưởng này trên một mô hình xác suất cụ thể.

Cho $N$ biến ngẫu nhiên độc lập. Biến thứ $i$ nhận giá trị là một số nguyên bất kỳ trong đoạn $[L_i;R_i]$, mỗi giá trị trong đoạn có cùng xác suất ${\displaystyle \frac{1}{R_i-L_i+1}}$.

Xét một bộ giá trị cụ thể của $N$ biến này. Ta đếm xem có bao nhiêu giá trị trong bộ có chữ số đầu tiên bằng $1$. Nếu số lượng đó chiếm ít nhất $K\%$ trong tổng số $N$ giá trị thì bộ giá trị được gọi là tốt.

Hãy tính xác suất để bộ giá trị của $N$ biến ngẫu nhiên đã cho là một bộ tốt.

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$ là số lượng biến ngẫu nhiên.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $L_i$ và $R_i$ mô tả biến ngẫu nhiên thứ $i$.
• Dòng cuối chứa số nguyên $K$.

Dữ liệu ra

In ra xác suất cần tìm. Kết quả đượ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}^{-9}$.

Ràng buộc

• $1\le N\le 1000$
• $1\le L_i\le R_i\le {10}^{18}$
• $0\le K\le 100$

Ví dụ