P1743 Matrix III

Adapted series problem by usqwedf.

Given an $n \times m$ matrix, ask how many paths there are from the top-left corner to the bottom-right corner. Retain 17 significant digits (that is, starting from the 18th significant digit, output 0).

A single line with two positive integers $n, m$.

The number of paths $t$.

Constraints: $1 \le n \le 10^8, 1 \le m \le 4$. Translated by ChatGPT 5