 <p>This is a Java solution that computes the ways by basically counting them one by one. One billion ways is computed in ~ 8 seconds.</p> <pre><code>long compute(int N, int M, int[] positions, int[] dimensions) { if (M == 0) { return 1; } long sum = 0; for (int i = 0; i &lt; N; i++) { if (positions[i] &lt; dimensions[i]) { positions[i]++; sum += compute(N, M - 1, positions, dimensions); positions[i]--; } if (positions[i] &gt; 1) { positions[i]--; sum += compute(N, M - 1, positions, dimensions); positions[i]++; } } return sum % 1000000007; } </code></pre>