Masala #0096

Xotira 32 MB Vaqt 1000 ms
14

Permutatsiya

Adizda [1,…,N] sonlar ketma-ketligi mavjud. U bu sonlarning barcha permutatsiyasini leksikografik o’sish tartibida qog’ozga yozib oldi va ularni ketma-ketligi bo’yicha raqamlab chiqdi. Masalan N=3 uchun jami 6 ta permutatsiya bor va ular quyidagilar:

Adiz bu permutatsiyalar orasidan ixtiyoriy birini tanlab oldi va uni yodida saqladi. Bir necha kundan so’ng u o’zi tanlagan permutatsiyani qog’ozga yozmoqchi bo’lganida bildiki tanlagan permutatsiyasidagi ba’zi qiymatlar yodidan ko’tarilgan, qog’ozga yozish jarayonida u yodidan ko’tarilgan qiymatlar o’rniga 0 qiymatini yozdi. Shundan so’ng uni quyidagicha savol qiziqtirib qoldi, u tanlagan permutatsiya qog’ozdagi qaysi qatorlar bo’lishi mumkin.


Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(1 ≤ N ≤ 3*105) permutatsiyadagi elementlar soni. Keyingi qatorda N ta butun son, Adizning yodida saqlagan permutatsiyasi.


Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, Adiz yodida saqlagan permutatsiya mos kelishi mumkin bo’lgan qog’ozdagi qatorlarning qiymatlari yig’indisini 109+7 ga bo’lgandagi qiymatini chop eting.


Misollar
# input.txt output.txt
1
4
0 2 3 0
23
2
4
4 3 2 1
24