Pyy just get his bonus from Minieye, he is happy, so he wants to do some programming to celebrate this. He considers Yanghui Triangle to be a good candidate for it can lead to many extensions.

  The original Yanghui Triangle represents like follows:

1

1 1

1 2 1

1 3 3 1

  But pyy wants to solve a more difficult problem, so he extends Yang Hui's Triangle as follows:

Line 0: a b

Line 1: a a+b b

Line 2: a 2a+b a+2b b

  Now pyy wants to know the sum of numbers which are on the slant line (numbers of the right most one) in Extended Yang Hui's Triangle.

We have multiply cases. For each cases:

The only one line contains five integers:

 a, b -- To define the extend Yanghui's Triangle.(1 <= a, b <= 1e9)

 x, y, z -- the slant line from [x,z] to [y,z], which is labeled from zero.(1 <= x <= y <= 1e7, 0 <= z <= x + 1)

The sum we need. But the sum may be huge, you should output the sum modulo 1000000007

2 3 0 1 1

8