Пусть p(n) представляет собой число различных способов, которыми можно разделить монеты на несколько столбиков. К примеру, пять монет можно разделить на несколько столбиков ровно семью различными способами, таким образом p(5) = 7.

Найдите наименьшее значение n для которого p(n) делится на один миллион без остатка.