C. Мокрая Акула и цветы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В подчинении у Мокрой Акулы находится n акул, сидящих за круглым столом. Таким образом, соседями являются акулы с номерами i и i + 1 для всех i от 1 до n - 1, а так же акулы с номерами 1 и n.

Каждая акула в течение дня вырастит случайное количество цветков si — целое число от li до ri, при этом все варианты равновероятны. У Мокрой Акулы есть любимое простое число p, от которого он совершенно без ума! Если для какой-то пары соседних акул i и j произведение количества выращенных ими цветков si·sj делится на p, то Мокрая Акула радуется и даёт каждой из этих акул по 1000 бурлей.

В конце дня акулы собираются вместе и складывают все подаренные бурли. Вычислите математическое ожидание этого количества.

Входные данные

В первой строке входных данных записаны целые числа n и p (3 ≤ n ≤ 100 000, 2 ≤ p ≤ 109) — количество акул и любимое простое число Мокрой Акулы соответственно. Гарантируется, что p является простым числом.

Каждая из последующих n строк содержит описание одной акулы. В i из них записаны числа li и ri (1 ≤ li ≤ ri ≤ 109) — диапазон возможного количества цветов, выращенных i-й акулой. Не забудьте, что реальное количество цветов выбирается равновероятно на этом отрезке, включая границы.

Выходные данные

Выведите единственное вещественное число — математическое ожидание суммарного количества бурлей, которое получат акулы. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.

А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если .

Примеры
Входные данные
3 2
1 2
420 421
420420 420421
Выходные данные
4500.0
Входные данные
3 5
1 4
2 3
11 14
Выходные данные
0.0
Примечание

Положительное целое число называется простым, если оно не делится ни на какое другое положительное целое число, кроме себя и 1. При этом число 1 простым не является.

Рассмотрим первый пример из условия. Первая акула выращивает от 1 до 2 цветков, вторая от 420 до 421, а третья от 420420 до 420421. Возможны восемь вариантов количества выращенных цветков (s0, s1, s2):

  1. (1, 420, 420420): 1·420 = 420, 420·420420 = 176576400 и 420420·1 = 420420. Каждая акула в каждой паре получит по 1000 бурлей, то есть в итоге каждая акула получит по 2000 бурлей, и сумма будет равна 6000 бурлей.
  2. (1, 420, 420421): В этом варианте 420421·1 не делится на 2, поэтому первая и третья акулы получат только по 1000 бурлей, а вторая всё ещё получит 2000. Итоговая сумма — 4000 бурлей.
  3. (1, 421, 420420): сумма 4000
  4. (1, 421, 420421): сумма 0.
  5. (2, 420, 420420): сумма 6000.
  6. (2, 420, 420421): сумма 6000.
  7. (2, 421, 420420): сумма 6000.
  8. (2, 421, 420421): сумма 4000.

Математическое ожидание равняется .

Во втором примере никакая комбинация количества цветов не приносит акулам бурлей.