Задача 07K. Марковские коты ≡

Условие

Вам выпала уникальная возможность исследовать популяцию марковских котов. Известно, что существует N пород, а также начальный размер популяции — количество особей каждой породы x_i ∈ N₀, i = 1, N. Марковские коты также обладают уникальной особенностью — каждый день ровно в полночь каждая отдельная особь породы i с вероятностью p_i,j независимо от остальных трансформируется в k_i,j ∈ N₀ особей породы j, при этом N∑j = 1p_i,j = 1. В качестве отчёта Вам требуется предоставить размер популяции в полночь через T дней наблюдений. Естественно, Вам не хочется бегать за котами и считать их вручную, поэтому Вы решаете ограничиться математическим ожиданием, ведь никто точно не захочет проверить предоставленный Вами отчёт, даже если количество особей будет нецелым.

При решении задачи необходимо использовать библиотеку numpy.

Формат входных данных

Первая строка входного файла содержит два целых числа N, T — количество пород и дней наблюдений соответственно. В следующих N строках содержится по N вещественных чисел — вероятности p_i,j. В следующих N строках содержится по N целых чисел — количества k_i,j. Последняя строка файла содержит N целых чисел x_i — начальный размер популяции.

Формат выходных данных

Выходной файл должен содержать N вещественных чисел — математическое ожидание размера популяции с точностью не менее 3-х знаков после запятой.

Ограничения

2 ⩽ N ⩽ 500

1 ⩽ T ⩽ 15

0 ⩽ k_i,j ⩽ 5

0 ⩽ x_i ⩽ 10

Примеры тестов

2 10
0 1
1 0
0 1
2 0
1 1

32 32

2 5
  1   0
0.5 0.5
1 0
2 4
1 1

32 32

2 5
0.9 0.1
0.5 0.5
1 0
5 1
0 2

6.9905 0.0625