F. Онцгой матрицууд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Дараах нөхцлүүдийг хангадаг $n × n$ хэмжээтэй квадрат матрицыг онцгой матриц гэнэ:

  • нүд бүр нь $0$ эсвэл $1$-ийн цифр агуулсан байна.
  • мөр болон багана бүрт яг $2$ ширхэг $1$-ийн цифр байна.

Танд $n$ тоо болон матрицын эхний $m$ ширхэг мөрүүд өгөгдөнө. Эхний $m$ мөрүүд нь өгөгдсөн $m$ мөрүүдтэй давхацдаг $n × n$ онцгой матрицуудын тоог хэвлэ. Шаардсан утга хэтэрхий том байж болох тул өгөгдсөн $mod$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Оролт

Оролтын эхний мөр нь $n$, $m$, $mod$ гэсэн ($2 ≤ n ≤ 500$; $0 ≤ m ≤ n$; $2 ≤ mod ≤ 10^{9}$) гурван бүхэл тоог агуулна. Дараа нь $m$ тооны мөр байх ба мөр бүр $n$ ширхэг тэмдэгтүүд агуулна. Энэ нь шаардсан онцгой матрицын эхний мөрүүд юм. Эдгээр мөр бүр яг хоёр ширхэг "1"-ийн тоо агуулах бөгөөд үлдсэн тэмдэгтүүд нь "0" байна. Өгөгдсөн $m × n$ хүснэгтийн багана бүр хамгийн ихдээ хоёр ширхэг "1"-ийн тоо агуулна.

Гаралт

Шаардсан утгыг $mod$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 1 1000
011
Гаралт
2
Оролт
4 4 100500
0110
1010
0101
1001
Гаралт
1

Тэмдэглэл

Эхний жишээнд шаардсан матрицууд нь:

011
101
110

011
110
101

Хоёр дахь жишээнд шаардсан матриц аль хэдийнээ бүрэн өгөгдсөн учраас хариулт нь $1$ байна.

Сэтгэгдлүүдийг ачааллаж байна...