Задание с матрицей

Алексей на первом курсе в университете изучает матрицы. Преподаватель дал им следующее задание.

Есть симметричная относительно главной диагонали квадратная матрица размером N×N с элементами a_ij.

Необходимо вычислить значение выражения:

В приведенном выражении перебираем T индексов [i₁ ... i_T], которые пробегают значения [1..N], и при этом суммируем по произведению всех T×(T - 1) / 2 возможных элементов матрицы, которые мы можем образовать с помощью этих индексов.

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

Входной файл INPUT.TXT содержит в первой строке два натуральных числа N, T (2 ≤ N ≤ 100; 2 ≤ T ≤ 5). Далее N строк содержат по N чисел a_ij (-10 ≤ a_ij ≤ 10).

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

В выходной файл OUTPUT.TXT выведите ответ на задачу по модулю 10⁹ + 7.

Пример

Пояснение к примеру

№	(i1, i2, i3)	ai2i1	ai3i1	ai3i2	Произведение	Сумма накопитель
1	(1, 1, 1)	6	6	6	216	216
2	(1, 1, 2)	6	2	2	24	240
3	(1, 1, 3)	6	-1	-1	6	246
4	(1, 2, 1)	2	6	2	24	270
5	(1, 2, 2)	2	2	2	8	278
6	(1, 2, 3)	2	-1	7	-14	264
7	(1, 3, 1)	-1	6	-1	6	270
8	(1, 3, 2)	-1	2	7	-14	256
9	(1, 3, 3)	-1	-1	5	5	261
10	(2, 1, 1)	2	2	6	24	285
11	(2, 1, 2)	2	2	2	8	293
12	(2, 1, 3)	2	7	-1	-14	279
13	(2, 2, 1)	2	2	2	8	287
14	(2, 2, 2)	2	2	2	8	295
15	(2, 2, 3)	2	7	7	98	393
16	(2, 3, 1)	7	2	-1	-14	379
17	(2, 3, 2)	7	2	7	98	477
18	(2, 3, 3)	7	7	5	245	722
19	(3, 1, 1)	-1	-1	6	6	728
20	(3, 1, 2)	-1	7	2	-14	714
21	(3, 1, 3)	-1	5	-1	5	719
22	(3, 2, 1)	7	-1	2	-14	705
23	(3, 2, 2)	7	7	2	98	803
24	(3, 2, 3)	7	5	7	245	1048
25	(3, 3, 1)	5	-1	-1	5	1053
26	(3, 3, 2)	5	7	7	245	1298
27	(3, 3, 3)	5	5	5	125	1423

Автор задачи

Владимир Игоревич Лукьянчиков

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]