Número de caminhos numa grelha
Imagine que tem uma grelha de altura
h e largura w. É-lhe pedido que calcule quantos percursos únicos podem ser feitos do canto superior esquerdo até ao canto inferior direito. Só é permitido deslocar-se para a direita e para baixo.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. O resultado pode ser muito grande, por isso deve ser calculado módulo .
Exemplos
Entrada | Saída |
2 3 | 3 |
3 4 | 10 |
7 3 | 28 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB