Find Products of Elements of Big Array
The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. It can be proven that the powerful array of x is unique.
The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so on. Thus, big_nums begins as [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...].
You are given a 2D integer matrix queries, where for queries[i] = [fromi, toi, modi] you should calculate (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi.
Return an integer array answer such that answer[i] is the answer to the i^th query.
Example 1
Input
queries = [[1,3,7]]Output
[4]There is one query, and
big_nums[1..3] = [2, 1, 2], whose product is 4, so 4 % 7 = 4.Example 2
Input
queries = [[2,5,3],[7,7,4]]Output
[2,2]For the first query,
big_nums[2..5] = [1, 2, 4, 1] gives 8 % 3 = 2, and for the second query, big_nums[7] = 2 gives 2 % 4 = 2.Constraints
- 1 <= queries.length <= 500
- queries[i].length == 3
- 0 <= queries[i][0] <= queries[i][1] <= 10^15
- 1 <= queries[i][2] <= 10^5