D. Квадратыг будах

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

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

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

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

Васили баавгайд $n$ мөр $n$ баганатай том квадрат цагаан хүснэгт байна. Хүснэгт нь тойроод хар хүрээтэй.

$n$ = $5$ байх анхны хүснэгтийн жишээ.

Васили баавгай яг $k$ хөдөлгөөнд өөрийн квадрат хүснэгтээ будахыг хүсч байна. Хөдөлгөөн бүр нь үйлдлүүдийн дараалал байна:

  1. Баавгай хүснэгтэн дотроосоо нэг квадрат сонгоно. Энэ квадрат нь тойроод хар хүрээтэй байх ёстой. Мөн квадрат нь хар нүд агуулаагүй байх ёстой. Квадрат доторх нүднүүдийн тоо нь $2$-с бага байж болохгүй.
  2. Баавгай сонгосон квадрат дотроосоо нэг мөр эсвэл нэг багана сонгоно. Тэгээд тэр сонгосон квадратын мөр, баганын нүд бүрийг будна. Үүний дараа квадратын хүрээ ба шинээр будагдсан нүднүүдээр хүрээлэгдсэн тэгш өнцөгтүүд нь хоосон биш талбайн квадрат байх ёстой.

$n$ = 7 ба $k$ = $2$ байх үеийн зөв будалтын жишээ.

Баавгай аль хэдийн $n$ ба $k$ тоонуудыг мэдэж байгаа. Түүнд квадратыг яг $k$ үйлдэлд будах боломжит замуудын тоог олж туслана уу. Хэрвээ үр дүнд нь гарч байгаа хүснэгтүүд ядаж нэг нүдээрээ ялгаатай байвал уг хоёр зам нь ялгаатайд тооцогдоно. Хариулт маш их тоо байж болох учир хариуг $7340033$ тоонд хуваагаад үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөрөнд бүхэл тоон утга $q$ $(1 ≤ q ≤ 10^{5})$ байх ба тестийн өгөгдлүүдийн тоо байна.

Дараагийн $q$ мөр бүрт хоёр бүхэл тоон утга $n$ ба $k$ $(1 ≤ n ≤ 10^{9}, 0 ≤ k ≤ 1000)$ байх буюу анхны хүснэгтийн хэмжээ ба харгалзах тестийн хөдөлгөөний тоо байна.

Гаралт

Оролтын тест бүрийн хувьд хариултыг $7340033$ тоонд хуваагаад үлдэгдлийг хэвлэ. Тестүүдийн хариултуудыг оролтонд өгөгдсөн дарааллаар хэвлэнэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
8
1 0
1 1
3 0
3 1
2 0
2 1
3 2
7 2
Гаралт
1
0
1
1
1
0
0
4

Тэмдэглэл

$n = 7$ ба $k = 2$ байх тестийн будах боломжит бүх замууд нь:

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