Sinuca
Uma mesa de sinuca retangular ocupa a região , . Ela tem seis buracos: os quatro cantos e os pontos médios dos dois lados de comprimento . Suas coordenadas são
Uma bola, tratada como um ponto, começa em sem cair no buraco inicial. Ela é lançada para o interior da mesa, com as duas componentes da velocidade positivas.
A bola nunca perde energia. Sempre que atinge uma parede fora de um buraco, ela reflete perfeitamente: a componente da velocidade perpendicular à parede troca de sinal, e a componente paralela permanece igual. Cada reflexão conta como uma batida na parede.
Ao atingir qualquer buraco, a bola cai nele e seu movimento termina. Isso também vale para o buraco inicial, caso a bola volte a ele. Cair em um buraco não conta como uma batida na parede.
Dado um inteiro , determine quantas trajetórias distintas fazem a bola bater nas paredes exatamente vezes antes de cair em um buraco. Duas trajetórias são consideradas distintas se suas direções iniciais são diferentes; a velocidade da bola não importa. Direções nas quais a bola nunca cai em um buraco não devem ser contadas.
Input
A única linha da entrada contém um inteiro (), o número de batidas nas paredes antes de a bola cair em um buraco.
Output
Imprima um inteiro: a quantidade de trajetórias distintas que fazem a bola bater nas paredes exatamente vezes antes de cair em um buraco.
Samples
Sample 1
Input
0
Output
2
Existem duas trajetórias sem reflexões: de diretamente para ou para .
Sample 2
Input
1
Output
3
As três trajetórias válidas passam, respectivamente, pelo ponto de reflexão na parede direita, por na parede direita ou por na parede superior. Depois dessa única reflexão, elas caem nos buracos , e .