Minimum S3 Storage Cost

A batch contains files numbered from 1 to 2^n. Some files are sensitive and require encryption; their indices are given in sensitiveFiles.
For any contiguous batch of M files:
If it contains X > 0 sensitive files, storing the whole batch costs M * X * encCost.
If it contains no sensitive files, storing the whole batch costs flatCost.
If the batch size is even, you may either store the whole batch or split it into two equal contiguous batches and pay the sum of their optimal costs. Return the minimum possible storage cost modulo 1_000_000_007.

Function
minStorageCost(n: int, encCost: int, flatCost: int, sensitiveFiles: int[]) → int

Examples
Example 1
n = 2
encCost = 2
flatCost = 1
sensitiveFiles = [1,3]
return = 6
Splitting all the way to single files costs 2 + 1 + 2 + 1 = 6, which is better than keeping the full batch or only splitting once.
Example 2
n = 3
encCost = 2
flatCost = 1
sensitiveFiles = [1,2,3,4,5,6,7,8]
return = 16
Every file is sensitive. Splitting into single files gives eight batches, each costing 2.
Example 3
n = 3
encCost = 2
flatCost = 1
sensitiveFiles = [7,1]
return = 8
One optimal split is [1], [2], [3,4], [5,6], [7], and [8], for total cost 8.

Constraints
1 <= n <= 3 * 10^5
1 <= encCost, flatCost <= 10^5
1 <= sensitiveFiles.length <= 2^n
Each sensitive file index is between 1 and 2^n.

The trick: n can reach 3*10^5, so 2^n is astronomically large and you can't walk the range. But sensitiveFiles has limited length. Any segment with zero sensitive files costs flatCost, and splitting it never helps, since two flat halves cost 2*flatCost. So recurse only into segments that contain sensitive files, and answer empty segments in O(1). Count sensitive files in a segment by sorting the indices and using binary search, or by partitioning the sorted list as you recurse. For each segment, cost = min(M*X*encCost, cost(left)+cost(right)). Size-1 segments can't split. The pitfall is computing M*X*encCost with huge M. Take the modulo for the final answer, but compare true minimums carefully, because a modded value can't be compared reliably. Use big numbers or cap the values. If you freeze on that comparison during the live OA, StealthCoder can cover you.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.