Given an integer 1 <= N <= 100, and 1 <= MIN, MAX <= 10^5, how can I compute the number of ordered pairs (a_1, a_2, ..., a_N) such that MIN <= a_i <= MAX for any i, and gcd(a_1, a_i) = 1 for any i not equal to 1?
For example, when N = 3, MIN = 2, and MAX = 4, the valid configurations are (2,3,3), (3, 2, 2), (3, 4, 2), (3, 4, 4), (4, 3, 3), and (3, 2, 4), so the output should be "6".
I am pretty sure (not 100%) this is a DP problem, but I can't manage to come up with the solution. Also, obviously, every configuration with the first number prime is valid, but this doesn't have to be the case. Does anyone have any ideas? I have been stuck on this problem for a few days now. Maybe I'm going about it wrong, and there is a really simple solution? Print the answer modulo 10^9 + 7.
Side-note: Is it possible to get TeX to work in these blogs?