Улаанбаатар хотод скутерийн үйлчилгээг нэвтрүүлснээс хойш иргэд зам
тээврийн осол гаргах, хүний скутерийг хулгайлах гэх мэт гэмт хэргүүдийг
хийх болжээ. Иймд хотын дарга скутерт дугаар олгох шийдвэр гаргажээ.
Сар бүрийн эхний өдөр хотын дарга n натурал тоог бодож олоод a1 + a2 + ...
+ ak = n байх бүх боломжит тоонуудаар [УБ a1 ; a2 ; ... ; ak] гэсэн дугааруудыг
хэвлэдэг. ai натурал тоонууд нь үл буурахаар эрэмбэлэгдсэн байна (a1 ≤ a2
≤ ... ≤ ak). Дугаар бүр давтагдашгүй байна. Ижил дугаартай хоёр скутер байж болохгүй.
Дугааруудыг скутер эзэмшигчдэд өгнө. Хэрэв хэн нэгэнд дугаар олдоогүй бол тэр сард
скутергүй хоцорно.
Хотын дарга өөрөө ч скутерээр явдаг. Түүний скутерийг хүмүүс шууд таньж байхын тулд
онцгой дугаартай байна. Тухайн сарын скутерийн [УБ a1 ; a2 ; ... ; ak] дугаар бүрийн хувьд
mex{a1 , a2 , ... , ak} буюу уг дугаарт байхгүй байгаа хамгийн бага натурал тоог олно. Эдгээр
тоонуудын нийлбэрийг олж 109 + 7 тоонд хувааж үлдэгдлийг олно. Энэ нь хотын даргын
скутерийн дугаар болох юм.
Энэ сард тэрээр n тоог сонгосон. Түүний скутерийн дугаарыг ол.
Оролт
Ганц мөрөнд энэ сард хотын даргын сонгосон натурал тоо n байрлана (1 ≤ n ≤ 1000).
Гаралт
Хотын даргын скутерийн дугаар болох энэ сарын скутерийн дугааруудын mex тоонуудын
нийлбэрийг 109 + 7 тоонд хуваасны үлдэгдэл болох 0-ээс 109 + 6 хүртэлх утгатай ганц тоог
хэвлэнэ.
Жишээ
Улаанбаатар хотод скутерийн үйлчилгээг нэвтрүүлснээс хойш иргэд зам
тээврийн осол гаргах, хүний скутерийг хулгайлах гэх мэт гэмт хэргүүдийг
хийх болжээ. Иймд хотын дарга скутерт дугаар олгох шийдвэр гаргажээ.
Сар бүрийн эхний өдөр хотын дарга n натурал тоог бодож олоод a1 + a2 + ...
+ ak = n байх бүх боломжит тоонуудаар [УБ a1 ; a2 ; ... ; ak] гэсэн дугааруудыг
хэвлэдэг. ai натурал тоонууд нь үл буурахаар эрэмбэлэгдсэн байна (a1 ≤ a2
≤ ... ≤ ak). Дугаар бүр давтагдашгүй байна. Ижил дугаартай хоёр скутер байж болохгүй.
Дугааруудыг скутер эзэмшигчдэд өгнө. Хэрэв хэн нэгэнд дугаар олдоогүй бол тэр сард
скутергүй хоцорно.
Хотын дарга өөрөө ч скутерээр явдаг. Түүний скутерийг хүмүүс шууд таньж байхын тулд
онцгой дугаартай байна. Тухайн сарын скутерийн [УБ a1 ; a2 ; ... ; ak] дугаар бүрийн хувьд
mex{a1 , a2 , ... , ak} буюу уг дугаарт байхгүй байгаа хамгийн бага натурал тоог олно. Эдгээр
тоонуудын нийлбэрийг олж 109 + 7 тоонд хувааж үлдэгдлийг олно. Энэ нь хотын даргын
скутерийн дугаар болох юм.
Энэ сард тэрээр n тоог сонгосон. Түүний скутерийн дугаарыг ол.
Оролт
Ганц мөрөнд энэ сард хотын даргын сонгосон натурал тоо n байрлана (1 ≤ n ≤ 1000).
Гаралт
Хотын даргын скутерийн дугаар болох энэ сарын скутерийн дугааруудын mex тоонуудын
нийлбэрийг 109 + 7 тоонд хуваасны үлдэгдэл болох 0-ээс 109 + 6 хүртэлх утгатай ганц тоог
хэвлэнэ.
Жишээ
Оролт: 2 Гаралт: 3
Оролт: 5 Гаралт: 14
Тайлбар: Эхний тестийн хувьд скутеруудын бүх боломжит дугаарууд нь [УБ 1;1] болон [УБ2] байх ба эдгээр дугааруудын mex тоонууд нь харгалзан 2 ба 1 байна.
Иймд хотын даргын скутерийн дугаар 2+1 = 3 байна. Хоёр дахь тестийн хувьд скутеруудын бүх боломжит дугаарууд болон тэдгээрийн mex
тоонуудыг доорх хүснэгтэд үзүүлэв:
