Партиција позитивног природног броја \(n\) је растављање броја \(n\) на збир неколико позитивних природних бројева при чему је редослед сабирака небитан (стога можемо претпоставити да је тај редослед или увек нерастући или увек неопадајући). На пример, ако је редослед нерастући, партиције броја \(4\) су \(1+1+1+1\), \(2+1+1\), \(2+2\), \(3+1\), \(4\). Написати програм који одређује број партиција за дати природан број \(n\).

Улаз

Прва и једина линија стандардног улаза садржи природан број \(n\) (\(n \leq 100\)).

Излаз

На стандардном излазу приказати у првој линији број партиција природног броја \(n\).

Пример 1

Улаз

6

Излаз

11

Објашњење

Ако су партиције са неопадајуће сортираним сабирцима, то су партиције:

1+1+1+1+1+1
1+1+1+1+2
1+1+1+3
1+1+2+2
1+1+4
1+2+3
1+5
2+2+2
2+4
3+3
6

Пример 2

Улаз

100

Излаз

190569292