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.