Carreras de caracoles
Mis colegas y yo solemos organizar carreras de caracoles. Es una afición de lo más tranquila. Cada uno trae a su caracol, al que ha alimentado con las mejores lechugas que ha encontrado; le ha dado mucha agua durante las últimas horas para que no se deshidrate durante la carrera; y, en definitiva, ha entrenado de la mejor forma posible.
Cuando todos los caracoles están preparados, son colocados en la línea de salida y el juez de la carrera (uno de nosotros elegido por sorteo) da el pistoletazo de salida. Y a partir de ahí… bueno, a veces la carrera pierde algo de emoción.
Para no terminar todos dormidos, Pablo nos ha propuesto calcular de cuántas formas distintas podría terminar el marcador. Hay que tener en cuenta que hay caracoles que pueden alcanzar la meta a la vez. Por ejemplo, si tenemos dos caracoles, C y D, hay tres posibles resultados: los dos llegan a la vez en primera posición, C queda primero y D segundo o D queda primero y C segundo.
¿Nos ayudas a calcular cuántos marcadores son posibles si la carrera consta de N caracoles?
Entrada
El programa deberá dar respuesta a una serie de casos de prueba. Cada caso está formado por una línea con un único entero (entre 1 y 3.000) que representa el número de caracoles participando en la carrera.
Salida
Para cada caso de prueba el programa deberá escribir el número de marcadores diferentes que se pueden dar al finalizar la carrera. Como el resultado puede ser muy grande, se escribirá módulo 46.337.
Entrada de ejemplo
1 2 3
Salida de ejemplo
1 3 13