Програмчлалын олимпиадын бодлогын архив

Хөршүүд

Энгийн чиглэлгүй N оройтой граф өгөгдсөн. Өөр лүүгээ орсон ирмэг байхгүй, мөн 2 оройн хооронд хамгийн ихдээ ганц ирмэг байдаг графыг энгийн граф гэнэ. Орой болгон дээр нэгэн эерэг тоо (<=500) өгөгдсөн. Нэг раундийн дараа орой болгон дээрх тоо дараах дүрмээр өөрчлөгдөнө:

Бүх хөршүүдийн өмнөх раундын тооны нийлбэр нь тухайн орой дээрх шинэ тоо болно. Ирмэгээр холбогдсон бол хөрш гэж үзнэ.

Тэгвэл K раундийн дараах бүх орой дээрх тоог ол.

Оролт:

N,K - тоо

NxN А матрыц өгөгдсөн. Хэрэв A(i,j)=1 бол i болон j-ээр оройнууд ирмэгээр холбогдсон, үгүй бол А(i,j)=0.Мөн үргэлж A(i,j)=A(j,i) байна.

Нэг мөрөнд орой болгон дээр бичигдсэн тоо.

Гаралт:

Нэг мөрөнд зайгаар тусгаарлагдсан К-раундийн дараах N-ширхэг тоог (10^9+7) хуваагаад үлдэгдэл.

Хязгаарлалт:

1<=N<=50

1<=K<=10^9

Жишээ:

Оролт:

3 1

0 1 0

1 0 1

0 1 0

1 2 3

Гаралт:

2 4 2