Coins flip - MarisaOJ: Marisa Online Judge

Coins flip

Time limit: 1000 ms
Memory limit: 256 MB
There are $n$ coins arranged in a row. On the $i^{th}$ coin, there is number $A_i$ written on the head face and $B_i$ written on the tail face. Let's denote function $f(l, r)$ as the maximum possible sum of coins $l, l + 1, ...,r$ that is not divisible by $k$. You can flip the coin as you wish. If there is no way to flip the coins then $f(l, r)=0$. Calculate: $$ \sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) $$ ### Input - The first line contains two integers $n, k$. - The next $n$ lines, the $i^{th}$ line contains two integers $A_i, B_i$. ### Output - Print the result, modulo $10^9+7$. ### Constraints - $1 \le n \le 10^5$. - $1 \le A_i, B_i,k \le 10^9$. ### Example Input: ``` 3 3 1 2 2 3 3 1 ``` Output: ``` 23 ```