Гурт друзів мандрував велосипедами по місцевості, що має спрощену схематичну мапу, яка подана на малюнку. Рухалися вони тільки у двох напрямках: схід або південь.  Села й міста на цій мапі зазначено маленькими колами, а шляхи – рисочками. Зупинившись на ночівлю в селі, яке на мапі має координати (1,1)  друзі почали обмірковувати свій подальший маршрут і засперечалися про шлях. Щоб покласти край суперечкам, один із друзів і каже:            
   – А знаєте, що я вигадав! Нас же багацько, ми можемо роз'їхатися нарізно, і кожний поїде іншим шляхом, ніж решта. З'їхавшись знову всі докупи, ми вже надалі знатимемо, який шлях найкращий. Ця пропозиція дуже сподобалася юнацтву, але знайшовся один, що любив математику. Подивившись уважно на мапу, він заперечив:                                                 
   –  Не буде діла, – сказав він. – На жаль, нас не вистачить на те щоб проїхати всіма можливими маршрутами. Знаєте скількома різними способами можна проїхати до того міста куди ми мандруємо? 1001 способом! Отже покиньте вашу витівку та давайте-но оберемо якийсь один шлях, щоб їхати всім укупі.              
   Чи не зумієте ви знайти на мапі мету мандрівки друзів, знаючи, що до неї веде 1001 шлях?

Вхідні дані:

   У вхідному стандартному потоці записано єдине число N, кількість маршрутів до деякого міста.