На вечеринке присутствует n людей. Каждый человек может присоединиться к танцу в одиночку или в паре с любым другим. Найдите количество различных способов, которыми все n человек могут присоединиться к танцу.
\InputFileОдно целое число n (1≤n≤105).
\OutputFileВыведите количество различных способов, которыми все n человек могут присоединиться к танцу. Выведите ответ по модулю 109+7.
\ExampleПусть имеется n=3 людей. Они могут присоединиться к танцу 4 способами: {1,2,3},{{1,2},3},{1,{2,3}},{{1,3},2}.