AT_abc473_e [ABC473E] K-Divisible Subarrays

You are given a sequence of length $ N $ consisting of non-negative integers: $ A=(A _ 1,A _ 2,\ldots,A _ N) $ . Define the **score** of a sequence of length $ 1 $ or more consisting of sequences of non-negative integers, $ S=(S _ 1,S _ 2,\ldots,S _ k) $ , as the number of sequences $ S _ i\ (1\le i\le k) $ whose sum of elements is divisible by $ K $ . Find the maximum possible score of a sequence of non-negative integer sequences obtained by dividing $ A $ into one or more contiguous subsequences. Here, dividing a sequence $ A $ of length $ N $ into one or more contiguous subsequences means choosing a sequence of integers $ l=(l _ 1,l _ 2,\ldots,l _ k)\ (1=l _ 1\lt l _ 2\lt\cdots\lt l _ k\le N) $ of length $ 1 $ or more, and forming the following $ k $ sequences. - $ (A _ {l _ i},A _ {l _ i+1},\ldots,A _ {l _ {i+1}-1})\ (1\le i\le k) $ (Here, let $ l _ {k+1}=N+1 $ .)

The input is given from Standard Input in the following format: > $ N $ $ K $ $ A _ 1 $ $ A _ 2 $ $ \ldots $ $ A _ N $

Output the answer.

### Sample Explanation 1 For example, $ A $ can be divided into four contiguous subsequences as $ (6),(8,2),(2),(6,4) $ . The sums of the elements of the second and fourth sequences are multiples of $ 10 $ , so the score of $ ((6),(8,2),(2),(6,4)) $ is $ 2 $ . $ A $ cannot be divided so that the score is $ 3 $ or more, so output `2`. ### Constraints - $ 1\le N\le2\times10 ^ 5 $ - $ 1\le K\le10 ^ 9 $ - $ 0\le A _ i\lt K $ - All input values are integers.