Count Index Triplets With an Even Product Modulo a Given Number

Given an integer array nums, count the triplets of indices (i, j, k) with i < j < k for which the product nums[i] * nums[j] * nums[k] is even. Because the count can be large, the original question required the result modulo a fixed number; here that number is passed in as mod, and you return the count modulo mod.

Function Signature

def count_even_product_triplets(nums: list[int], mod: int) -> int:

Rules

• A triplet is a choice of three different positions, counted once in the order i < j < k. Equal values at different positions form different triplets.
• An integer is even when it is divisible by 2. Zero is even, and negative numbers follow the same rule: -4 is even and -3 is odd.
• If nums has fewer than three elements, the answer is 0.
• Return a value in the range [0, mod - 1].

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• 2 <= mod <= 10^9 + 7
• Before the modulo, the count can reach about 1.7 * 10^14, which exceeds the 32-bit signed range but stays below 2^53. A product of three values can reach 10^27, which exceeds the 64-bit range.

Examples

Example 1

Input:  nums = [1, 2, 3, 4], mod = 1000000007
Output: 4

All four triplets have an even product.

Example 2

Input:  nums = [5, 7, 9, 2, 11], mod = 1000000007
Output: 6

Only the triplets that include index 3 (value 2) have an even product, and there are 6 of them.

Example 3

Input:  nums = [2, 4, 6, 8, 10, 1], mod = 9
Output: 2

All 20 triplets have an even product, and 20 modulo 9 is 2.

Count Even-Product Index Triplets Modulo mod

Given an integer array nums and an integer mod, count the triplets of indices (i, j, k) with i < j < k for which the product nums[i] * nums[j] * nums[k] is even, and return that count modulo mod.

Rules

• A triplet is a choice of three different positions, counted once in the order i < j < k. Equal values at different positions form different triplets.
• An integer is even when it is divisible by 2. Zero is even, and negative numbers follow the same rule: -4 is even and -3 is odd.
• If nums has fewer than three elements, the answer is 0.
• Return the count modulo mod, which is a value in the range [0, mod - 1].

Value ranges

Before the modulo, the count can reach about 1.7 * 10^14, which exceeds 2^31 - 1 (but stays below 2^53), so intermediate counts need 64-bit integers (long in Java, long long in C++). The returned value is below mod <= 10^9 + 7 and fits in a 32-bit int. A product of three values can reach 10^27, which exceeds the 64-bit range.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• 2 <= mod <= 10^9 + 7

Example 1

Input:  nums = [5, 7, 9, 2, 11], mod = 1000000007
Output: 6

Only the triplets that include index 3 (value 2) have an even product, and there are 6 of them.

Example 2

Input:  nums = [2, 4, 6, 8, 10, 1], mod = 9
Output: 2

All 20 triplets have an even product, and 20 modulo 9 is 2.

Hints

1. Only whether each value is even or odd affects whether a product is even. Zero and negative even numbers are even.
2. Ask when a product of three integers fails to be even.
3. The count before the modulo can exceed 2^31 - 1, and a product of three values can exceed the 64-bit range, so choose numeric types with care.

Approach

A product of integers is even exactly when at least one factor is even, so a triplet fails the condition only when all three of its values are odd. Count the odd values o in one pass, testing x % 2 != 0; that test is correct for negative values in every language, whereas x % 2 == 1 misclassifies negative odds in JavaScript, Java and C++, where -3 % 2 is -1. There are C(n, 3) = n(n-1)(n-2)/6 index triplets in total and C(o, 3) = o(o-1)(o-2)/6 all-odd triplets, so the answer is (C(n, 3) - C(o, 3)) mod mod. Correctness: every triplet is either all-odd (odd product) or contains an even value (even product), and these two groups are disjoint and together cover all C(n, 3) triplets. Equal values at different positions are distinct triplets automatically, because the formulas count positions rather than values. Because C(o, 3) <= C(n, 3), the difference is non-negative, so one final modulo gives a value in [0, mod - 1] in every language; reducing each term separately and subtracting could go negative. The pre-modulo count is at most C(10^5, 3), about 1.67 * 10^14, and the intermediate n(n-1)(n-2) stays below 10^15 < 2^53, so 64-bit integers and JavaScript doubles compute it exactly. No three-value product is ever formed, so its 10^27 magnitude never matters. Edge cases: one or two elements return 0 (guarded explicitly, and both formulas also yield 0 below 3); fewer than three odd values make C(o, 3) = 0; an all-odd array returns 0; an all-even array returns C(n, 3) mod mod; zero and negative even values count as even.

• Time complexity: O(n)
• Space complexity: O(1)