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