You are given a $0$ indexed string word of length n consisting of numeric digits, and a positive integer m.

The divisibility array div of word is an integer array of length n where:

• div[i] = 1 if the numeric value represented by the prefix word[0...i] is divisible by m

• div[i] = 0 otherwise

Return the divisibility array of word.

Constraints:

• $1 \leq n \leq 10^5$

• word.length $= n$

• word consists of digits from $0$ to $9$

• $1 \leq m \leq 10^9$

Input: word = "63015"-str, m = 3-int
Output: [1,1,1,0,1]-List[int]
Explanation: The prefixes 6, 63, and 630 are divisible by 3, 6301 is not, and 63015 is divisible by 3, producing [1,1,1,0,1].

Input: word = "1234567"-str, m = 11-int
Output: [0,0,0,0,0,0,0]-List[int]
Explanation: None of the prefixes of 1234567 is divisible by 11, so every entry is 0.

Input: word = "507"-str, m = 1-int
Output: [1,1,1]-List[int]
Explanation: Every integer is divisible by 1, so all prefixes produce an entry of 1.

Input: word = "004096"-str, m = 16-int
Output: [1,1,0,0,0,1]-List[int]
Explanation: The prefixes 0 and 00 are divisible by 16, the next three prefixes are not, and the full prefix 004096 is divisible by 16.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.