1681 - Extended Yang Hui's Triangle

Time Limit : 1 Second

Memory Limit : 512 MB

Submission: 11

Solved: 3

Description

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.

Input

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)

Output

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

sample input
2 3 0 1 1
sample output
8
hint
source
© 2015 HUST ACMICPC TEAM. All Right Reserved.