Scaler Subarrays II

You are given an array A of size N.

A subarray A [ l ... r ] contains all the elements A[l], A[l+1], .... , A[r]. A subarray A [ l ... r ] is called a scaler subarray if max( A [ l ... r ] ) and A[l] + A[r] are congruent modulo B.

Here, max( A [ l ... r ] ) is the maximum value of this subarray.

Given an integer n > 1, called a modulus, two integers a and b are said to be congruent modulo n, if n is a divisor of their difference (i.e. if there is an integer k such that

a − b = k n).

Find the total number of scaler subarrays of A. Since the answer can be large, return it modulo 10⁹ + 7.

1 <= N, B <= 5 x 10⁵

1 <= A[i] <= 10⁹

The first argument contains an integer array A of size N.

The second argument contains an integer B.

Return the number of scaler subarrays of A modulo 10⁹ + 7.

Input 1:

  A : [ 8, 7 ]
  B : 4

Input 2:

  A : [ 4, 5, 3, 8, 8 ]
  B : 5

Output 1:

  1

Output 2:

  3

Explanation 1:

  The subarray [8] is scaler because max([8]) = 8 and A[l] + A[r] = 16. 
  8 and 16 are congruent modulo 4 because 16 - 8 = 8 is divisible by 4.

Explanation 2:

  Scaler subarrays are [5], [5, 3, 8] and [5, 3, 8, 8].