Resolution Configurations

Problem Statement

Resolution Configurations Problem Description There are n computer frames. Frame i has a power power[i] . The current resolution starts at 1 . Each frame is independently left unused, or used in one of three ways: As a magnifying frame , which multiplies the current resolution by power[i] . As a reducing frame , which divides the current resolution by power[i] . Using both its magnifying and reducing powers together, which leaves the current resolution unchanged. So every frame has exactly four choices: unused, magnifying, reducing, or both. You are given q target resolutions. For each one, report how many configurations of the n frames produce exactly that resolution, modulo 10^9 + 7. It is not necessary to use all the frames. Two configurations are different if at least one frame is used in one and not in the other, or if some frame is used in a different way in the two. In particular, leaving frame 1 unused and using both of its powers together are two different configurations even