Пользователь ainta решил разрисовать стену. Стена состоит из n2 плиток, расположенных в виде таблицы размера n × n. Некоторые плитки окрашены, другие — нет. Юноша хочет покрасить стену красиво и поэтому будет красить ее по следующим правилам:
- Сначала пользователь ainta внимательно смотрит на стену. Если в каждой строке стены есть хотя бы одна окрашенная плитка, и в каждом столбце стены есть хотя бы одна окрашенная плитка, он прекращает покраску. В противном случае, он переходит к пункту 2.
- Пользователь ainta равновероятно выбирает любую плитку стены.
- Если выбранная плитка не окрашена, она красится. В противном случае она игнорируется.
- Затем ainta отдыхает одну минуту, даже если он не покрасил плитку в предыдущем пункте. После чего он переходит снова к пункту 1.
Все же ainta беспокоится, не слишком ли долго придется красить стену описанным алгоритмом. Поэтому он хочет подсчитать математическое ожидание затраченного времени при использовании описанного выше алгоритма покраски. Помогите ему. Можете считать, что на выбор и окраску плитки время не тратится.
Выходные данные
В единственной строке выведите математическое ожидание времени, необходимого на покраску стены, в минутах. Ваш ответ будет считаться правильным, если величина его абсолютной или относительной погрешности не превышает 10 - 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
2 3
4 1
|
11.7669491886
|
|
2
|
2 2
1 1
1 2
|
2.0000000000
|
|
3
|
1 1
1 1
|
0.0000000000
|