Company: UKG

There is an integer array arr[n] and an integer value d. The array is indexed from 1 to n. Count the number of distinct triplets (i, j, k) such that 0 < i < j < k ≤ n and the sum (a[i] + a[j] + a[k]) is divisible by d.

Example: a = [3, 3, 4, 7, 8], d = 5. The following triplets are divisible by d = 5. These are the triplets whose sum is divisible by d (1-based indexing):
· indices (1, 2, 3), s um = 3 + 3 + 4 = 10
· indices (1, 3, 5), sum = 3 + 4 + 8 = 15
· indices (2, 3, 4), sum = 3 + 4 + 8 = 15

Since there is no other triplet divisible by d = 5, return 3.

Function Description: Complete the function getTripletCount in the editor below.

getTripletCount has the following parameters:
int a[n]: an array of integers
int d: an integer

Returns: int — the number of distinct triplets

Constraints:
· 1 ≤ a[i] ≤ 10^9
· 2 ≤ d ≤ 10^9

Input Format For Custom Testing:
Sample Case 0

Sample Input For Custom Testing:
STDIN
2
FUNCTION
4
a = [2, 3, 1, 6]
1
6
3

Sample Output:
3 Show More

There is an array of n non-negative integers, arr. In one operation, some positive integer x is chosen and 1 is subtracted from all the numbers of the array which are greater than or equal to x. Find the number of different final arrays possible after the operation is applied 0 or more times. Return the answer modulo (10^9 + 7).

Note: 1-based indexing is used. Different values of x can be chose n for different operations. Two final arrays a and b are considered different if there is at least one i (1 ≤ i ≤ n) such that a[i] != b[i].

Example: Consider n = 2, arr = [1, 2]. There are four different final arrays possible. x = 0 operations yields [1, 2]. x = 1 yields [0, 1]. x = 2 yields [1, 1]. x = 2 and then x = 1 yields [0, 0]. Notice that choosing x = 1 and then x = 1 will give [0, 0] which has been counted already. So, the number of different final arrays achievable is 4. Return 4 modulo (10^9 + 7) which equals 4.

Function Description: Complete the function getCount in the editor below.

getCount has the following parameters:
int arr[n]: the original array

Returns:
int: the number of different final arrays achievable, modulo (10^9 + 7)

Constraints:
1 ≤ n ≤ 10^5
0 ≤ arr[i] ≤ 10^5

Input Format For Custom Testing

Sample Case 0
STDIN
3
2
1

Function: arr[] size n = 3, arr = [2, 1]
Sample Output: 4

Explanation: The four possible final arrays are shown
operation(s) -> result
0 operations -> [0, 2, 1]
x = 1 -> [0, 1, 0]
x = 2 -> [0, 1, 1]
x = 2 then x = 1 -> [0, 0, 0]

Sample Case 1
STDIN
4
2
3
0
2

Function: arr[] size n = 4, arr = [2, 3, 0, 2]
Sample Output: 6

Explanation:
No operations -> [2, 3, 0, 2]
x = 1 -> [1, 2, 0, 1]
x = 1 then x = 1 -> [0, 1, 0, 0]
x = 1 then x = 2 -> [1, 1, 0, 1]
x = 1, x = 2 then x = 1 -> [0, 0, 0, 0]
x = 3 -> [2, 2, 0, 2] Show More