Даалуу

Програмчлалын хамгийн мундаг аварга нь "Про Лигийн Аварга" гэдгийг мэдэх үү?

"Про лиг" -н мундаг залуус уйдахаараа даалуу өрж тоглодогт итгэж байна уу?

Мэдээж тэд энгийн даалуу өрдөг тоглоомоос арай хэцүү тоглоом тоглодог. Тэдний тоглоом $1$-ээс $N$ хүртэл дугаарлагдсан $1$x$N$ хэмжээтэй хөлөг дээр $1$-ээс $N$ өндөртэй даалууг өрдөг. Ингэхдээ

• Хөлөг дээр ядаж нэг даалуу байна

• Хөлгийн нэг нүдэнд $1$-ээс олон даалуу тавьж болохгүй

• Хөлгийн дараалсан $2$ нүдэнд даалуу тавьж болохгүй

• $i$ дугаар нүдэнд $i$-ээс өндөр даалуу тавьж болохгүй

• Ямар ч өндөртэй даалуунаас хэдэн ч ширхгийг ашиглаж болно

гэсэн маш энгийн дүрмүүдийг баримталдаг.

Тэгвэл тэд даалуугаа хэдэн ялгаатай янзаар өрж болох вэ?

Энд хөлгийн ядаж нэг нүдэн дэх даалуу нь ялгаатай байвал $2$ өрөлтийг ялгаатай гэж үзнэ. Өрөх дараалал хамаарахгүй.

Оролт

Дээр тодорхойлсон $N (N <= 31)$ тоо байна.

Гаралт

Нийт ялгаатай өрөлтийн тоог хэвлэнэ.

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

Тайлбар

$\{ (1,0,0),$
$\ $ $(0,1,0),$
$\ $ $(0,2,0),$
$\ $ $(0,0,1),$
$\ $ $(0,0,2),$
$\ $ $(0,0,3),$
$\ $ $(1,0,1),$
$\ $ $(1,0,2),$
$\ $ $(1,0,3) \}$