Bob runs a tile shop. He sells only square tiles. He charges $a per unit area and $b per unit length of its side. Moreover, he also charges a constant amount of $c for each tile. He asks you to calculate the total amount he gets after selling exactly one tile of side length x in range [l,r]. Bob knows that his earnings is beyond your calculation, so he asks you to calculate amount modulo (109+7).

First line contains number of test cases, T. Each test case contains 5 integers, a, b, c, l, r.

Output a single integer denoting answer as per the problem statement.