1
import numpy as np
2

3

4
class Solution:
5

6
    def checkRecord(self, n: int) -> int:
7
        MODULUS = 10**9 + 7
8

9
        initial_counts = np.array([1, 0, 0, 0, 0, 0], dtype=np.int64)
10

11
        adjacency_matrix = np.array(
12
            [
13
                [1, 1, 1, 0, 0, 0],
14
                [1, 0, 0, 0, 0, 0],
15
                [0, 1, 0, 0, 0, 0],
16
                [1, 1, 1, 1, 1, 1],
17
                [0, 0, 0, 1, 0, 0],
18
                [0, 0, 0, 0, 1, 0],
19
            ],
20
            dtype=np.int64,
21
        )
22

23
        def power(A, exp):
24
            B = np.identity(len(A), dtype=np.int64)
25
            for bit in reversed(bin(exp)[2:]):
26
                if bit == "1":
27
                    B = B @ A
28
                    B %= MODULUS
29
                A = A @ A
30
                A %= MODULUS
31
            return B
32

33
        final_counts = power(adjacency_matrix, n) @ initial_counts
34

35
        return sum(final_counts) % MODULUS