D. Сэлгэмэл нийлбэр

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

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

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

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

$p$ сэлгэмэл гэдэг нь бүхэл тоо $p_{1},  p_{2},  ...,  p_{n}$-уудын цэгцэлсэн олонлог бөгөөд ялгаатай $n$ ширхэг эерэг бүхэл тооноос тогтоно, мөн тэдгээр тоонууд тус бүр нь $n$-ээс хэтрэхгүй. Бид $p$ сэлгэмлийн $i$-дахь элементийг $p_{i}$ гэж тэмдэглэнэ. Бид $n$ тоог $p_{1},  p_{2},  ...,  p_{n}$ сэлгэмлийн хэмжээ эсвэл урт гэж нэрлэх юм.

Петя $n$ урттай сэлгэмлүүдийн олонлог дээр нийлбэрийн үйлдлийг танилцуулахаар шийджээ. Бидэнд $n$ урттай 2 сэлгэмэл өгөгдсөн гэж үзье: $a_{1}, a_{2}, ..., a_{n}$ болон $b_{1}, b_{2}, ..., b_{n}$. Петя $a$ болон $b$ сэлгэмлүүдийн нийлбэрийг $c_{i} = ((a_{i} - 1 + b_{i} - 1) mod n) + 1$ байх $n$ урттай $c$ сэлгэмэл гэж үзнэ $(1 ≤ i ≤ n)$.

үйлдэл нь $x$ тоог $y$ тоонд хуваасны дараах үлдэгдлийг илэрхийлэх юм.

Мэдээж хэрэг, бүх $a$ болон $b$ сэлгэмлүүдийн хувьд $a$ болон $b$-ын нийлбэр байх $c$ сэлгэмэл оршин байхгүй. Тиймээс Петя уйтгарласан ба таныг дараах зүйлсийг хийхийг хүсжээ: $n$ өгөгдөх ба $a$ болон $b$-ын нийлбэр байх $c$ сэлгэмэл оршин байх $n$ урттай $a$ болон $b$ хос сэлгэмлүүдийн тоог тоолно. Хос сэлгэмэл $x, y$ $(x ≠ y)$ болон хос сэлгэмэл $y, x$ нь ялгаатай хосууд гэж тооцогдоно.

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

Оролт

Ганц мөрөнд бүхэл тоо $n (1 ≤ n ≤ 16)$ өгөгдөнө.

Гаралт

Ганц мөрөнд сөрөг биш ганц бүхэл тоо хэвлэнэ -- энэ нь $a$ болон $b$-ын нийлбэр байх $c$ сэлгэмэл оршин байх $a$ болон $b$ хос сэлгэмлүүдийн тоог $1000000007$ ($10^{9} + 7$) модулаар бодсон утга байна.

Орчуулсан: Баатархүү

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

Оролт
3
Гаралт
18
Оролт
5
Гаралт
1800
Сэтгэгдлүүдийг ачааллаж байна...