[Python 148ms] Adjacent matrix power to compute number of walks
python\nimport numpy as np\nclass Solution:\n    def dieSimulator(self, N: int, rollMax: List[int]) -> int:\n        # for indexing convenience\n        rollMax
```python\nimport numpy as np\nclass Solution:\n    def dieSimulator(self, N: int, rollMax: List[int]) -> int:\n        # for indexing convenience\n        rollMax = [0] + rollMax\n        # list all possible states (last digit, number of consecutive)\n        states = [(0, 0)] + [\n            (i, c)\n            for i in range(1, 7)\n            for c in range(1, min(N, rollMax[i]) + 1)\n        ]\n        # give each state an index\n        num_state = len(states)\n        aux = {st: idx for idx, st in enumerate(states)}\n        # build one-step transition matrix\n        T = np.zeros((num_state, num_state), dtype=np.uint64)\n        for (i, c), idx in aux.items():\n            for j in range(1, 7):\n                if j != i and rollMax[j] > 0:\n                    T[idx, aux[(j, 1)]] = 1\n                elif j == i and c < min(N, rollMax[i]):\n                    T[idx, aux[(i, c + 1)]] = 1\n        # compute N-step transition matrix \n        T_N = np.zeros((num_state, num_state), dtype=np.uint64)\n        T_N[0, 0], MOD = 1, int(1e9 + 7)\n        # matrix multiplication avoid overflow\n        def myMatMul(A, B):\n            k, ans = 0, 0\n            stride = int(2 ** 64 - 1) // int((1e9 + 7 - 1) ** 2)\n            while k < num_state:\n                ans += np.dot(A[:, k:k + stride], B[k:k + stride, :]) % MOD\n                ans %= MOD\n                k += stride\n            return ans\n        # using log(N) matrix multiplication, same idea as integer power of scalar\n        while N:\n            N, odd = divmod(N, 2)\n            if odd: T_N = myMatMul(T_N, T) % MOD\n            T = myMatMul(T, T) % MOD\n        return int(T_N[0].sum()) % MOD\n```
[]