Partition
Национална Олимпиада по Информатика, Кръг 3
Time Limit: 0.2s, Memory Limit: 64MiB
Ели си взе нов лаптоп (може би малко обидна дума за ЧУДОВИЩЕТО, с което тя се сдоби). Това предизвика известно вълнение сред съучениците й, главно заради неговите характеристики. High-definition матрицата на монитора, 5 гигахерцовият 8 ядрен процесор, 64-те гигабайта DDR4 памет, и 100-терабайтовият SSD диск са само част от неговите екстри. Разбира се, това са нещата, на които другите се възхищават. Тя си го харесва, защото е розов.

Разбира се, разполагайки с такъв хардуер, човек неминуемо среща и проблеми. Например, сега момичето се чуди как да раздели харддиска си – колко място да остави за операционната система, колко за филми, за музика и т.н. Ели счита, че всеки дял (partition) трябва да е не по-малък от 3 гигабайта и да е цяло число. Помогнете й, като по зададен размер на харддиска определите по колко начина може да бъде разбит на дялове с размер A1, A2, ..., AK, къдетo A1 + A2 + ... + AK = N. Броят дялове K няма значение, стига да са изпълнени останалите условия (A1 + A2 + ... + AK = N, Ai ≥ 3).
Вход
На единствения ред на стандартния вход ще бъде зададен размерът на харддиска в гигабайти N.
Изход
На единствен ред на стандартния изход изведете по колко начина може да бъде разбит харддискът като сума на цели, положителни числа, не по-малки от три. Тъй като това число може да бъде много голямо, изпечатайте само неговия остатък по модул 1,000,000,007.
Ограничения
  • 3 ≤ N ≤ 100,000
Примерен Вход Примерен Изход
3 1
10 9
1337 667581228
Хард с размер 3 гигабайта можем да разбием само по един начин – на един партишън с размер 3 гигабайта. Забележете, че тъй като партишъните трябва да са с размер поне 3GB не е разрешено разбиването 1 + 2, например. Във втория тест възможните разбивания са: {3, 3, 4}, {3, 4, 3}, {4, 3, 3}, {4, 6}, {6, 4}, {3, 7}, {7, 3}, {5, 5}, {10}. В третия тест не забравяйте да изведете само остатъка на отговора при деление на един милиард и седем.
Мрън!