B. Хүснэгт

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

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

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

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

Жонн-д $n × m$ хүснэгт байгаа. Жонн хүснэгтийн зарим нүдийг цэгээр будаж чаддаг. Нэг нүдийг нэгээс илүү цэгээр буддаггүй. Тэр $n × n$ дэд хүснэгтэнд яг $k$ ширхэг цэг байлгамаар байгаа.

Дээрх нөхцөлийг хангах хэдэн ялгаатай хүснэгт байгааг танаас олж өгөхийг хүсэв. Энэ тоо маш их байж магадгүй учир $1000000007$-д $(10^{9} + 7)$ хуваасны үлдэгдлийг олно уу.

Жонн нэг нүдний яг голыг нь цэгээр буддаг. Хэрвээ хүснэгтний нэг будагдсан нүд нь өөр хүснэгтний ямар нэгэн байдлаар тэр нүд нь будагдаагүй бол энэ 2 хүснэгтийг ялгаатайд тооцно.

Оролт

Нэг мөрөнд $n$, $m$, $k$ ($1 ≤ n ≤ 100; n ≤ m ≤ 10^{18}; 0 ≤ k ≤ n^{2}$) хүснэгтийн мөрний тоо, хүснэгтийн баганы тоо, $n × n$ хүснэгт бүрд байх цэгийн тоо.

C++ дээр $cin$, $cout$ эсвэл %I64d -г ашиглана уу.

Гаралт

Хариу болох ганц тоог $1000000007$-д $(10^{9} + 7)$ хуваасны үлдэгдлийг хэвлэнэ үү

Орчуулсан: anhaabc

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

Оролт
5 6 1
Гаралт
45

Тэмдэглэл

Энэ жишээ нь:

Саарал хэсэг нь $5 × 5$ 2 хүснэгтэнд 2ланд нь агуулагдаж байна. Хэрвээ энэ хэсэгт цэг байвал бусад хэсэгт өөр цэг байж болохгүй тэгэхлээр 20 боломж байна. Хэрвээ нэг цагаан хэсэгт нь нэг цэг байвал нөгөөн цагаан хэсэгт нэг цэг байх ёстой болно тэгэхлээр 25 боломж байна. Иймээс хариу $20 + 25 = 45$ гарж байна.

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