Número de caminhos numa grelha 2
Dada uma grelha de altura
h e largura w, pretende-se determinar quantos percursos únicos se podem fazer para ir do canto superior esquerdo ao canto inferior direito. Só é permitido deslocar-se para a direita, para baixo ou na diagonal em direção ao canto inferior direito.o | ➡️ | ㅤ | ㅤ |
⬇️ | ↘ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | x |
Entrada
A entrada contém dois inteiros
h e w (1 ≤ h, w ≤ 100).Saída
O programa deve apresentar o número de caminhos únicos possíveis entre o canto superior esquerdo e o canto inferior direito da grelha. Como este valor pode ser muito elevado, o resultado deve ser calculado em módulo .
Exemplos
Input | Output |
2 3 | 5 |
3 4 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB