Masala #1061

Xotira 16 MB Vaqt 1000 ms
14

Qutilarni joylashtirish

MegaBoy yaqinda bir korxonaga ishga kirdi. Uning vazifasi qutilarni to'g'ri joylashtirish. Qutilar 1 dan n gacha raqamlangan. Ular to'g'ri joylashtirilgan hisoblanadi qachonki ularda hech qanday yonma-yon toq yoki juft qutilar bo'lmasa va tartib raqami bo'yicha o'sish tartibida joylashgan bo'lsa. Unda 1 dan n gacha raqamlangan n ta quti bor ularni to'g'ri joylashtirish mumkin bo'lgan barcha variantlar sonini toping.


Kiruvchi ma'lumotlar:

Kirish faylida yagona qatorda \(n(1\le n \le 10^6)\) soni kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida barcha variantlar sonini chop eting. Bunda javob juda katta bo'lishi mumkin shu sababdan 1000000007 ga bo'lgandagi qoldiqni chop eting.


Misollar
# input.txt output.txt
1
3
6
2
4
11
Izoh:

n = 3 bo'lgand:

  • 1
  • 2
  • 3
  • 1 2
  • 2 3
  • 1 2 3

Jami 6 xil

n = 4 bo'lganda

  • 1
  • 2
  • 3
  • 4
  • 1 2
  • 2 3
  • 3 4
  • 1 4
  • 1 2 3
  • 2 3 4
  • 1 2 3 4