Show problems as
Classic problem #2438MediumArrayBit ManipulationPrefix Sum

Range Product Queries of Powers

Real-world version: Products Over Stretches of the Binary Pieces
Tracked in this browser only
Read Range Product Queries of Powers on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

The number n can be written as a sum of powers of two, each used at most once, and in exactly one way. List those powers in increasing order and call the list pieces.

Each entry of queries is a pair [from, to] naming a stretch of pieces, both ends included. Answer each with the product of the pieces in that stretch, taken modulo 10^9 + 7.

Return the answers in the order the queries are asked.

Examples

Example 1

Input
n = 7, queries = [[0, 2]]
Output
[8]

Seven splits into 1, 2 and 4, and the whole stretch multiplies to 8.

Example 2

Input
n = 12, queries = [[0, 0], [1, 1]]
Output
[4, 8]

Twelve splits into 4 and 8, and each query asks for one of them on its own.

Example 3

Input
n = 255, queries = [[0, 7]]
Output
[268435456]

The eight pieces are the powers of two from 1 up to 128, so their exponents add to 28 and the product is two to that.

Constraints

  • 1 <= n <= 10^9
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= queries[i][0] <= queries[i][1]

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def product_queries(n: int, queries: list[list[int]]) -> list[int]:
Java
public int[] productQueries(int n, int[][] queries)

More on the same topics