19130번 - Long Binary Sequence 다국어

Bobo has a very very long binary sequence $s$ of length $n$. All except $m$ positions $x_1, x_2, \dots, x_m$ are $0$ (And $s_{x_1} = s_{x_2} = \dots = s_{x_m} = 1$).

Now bobo would like to know the number of distinct consecutive substrings of $s$.

The first line contains $2$ integers $n, m$ ($1 \leq n \leq 10^9, 1 \leq m \leq \min\{n, 1000\}$).

The second line contains $m$ integers $x_1, x_2, \dots, x_m$ ($1 \leq x_1 < x_2 < \dots < x_m \leq n$).

A single integer denotes the number of distinct substrings.