Цамхгуудыг Тоолох

2s

512MB

1209

0%

Dynamic Programming

Өргөн нь $2$ , өндөр нь $n$ цамхаг барина. Өргөн, өндөр нь бүхэл тоо болох блокуудыг хязгааргүй олноор ашиглаж болно.

Жишээ нь $n=6$ үед зарим боломжит шийдүүд:
image
$n$ өгөгдөхөд хэдэн өөр цамхаг барих боломжтой вэ? Толин тусгал, эргүүлсэн цамхгууд өөрөөр харагдаж байвал тус тусад нь тоолно.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд тестүүдийн тоо $t$ бүхэл тоо байна.

Үүний дараа $t$ мөр байна; мөр бүрт цамхгийн өндөр $n$ бүхэл тоо байна.

Гаралтын формат

Тест бүрт цамхгуудын тоог $10^9+7$ -д хуваасан үлдэгдлээр хэвлэ.

Хязгаарлалт

$1 \le t \le 100$
$1 \le n \le 10^6$

Жишээ

Оролт1

Гаралт1

8
2864
640403945

0.1 / 64 KiB

Редактор уншиж байна...