**Code A Thon SOLUTIONS 2020**

**Code A Thon SOLUTIONS 2020**

Problem Statement

An issue is given to Piyush that, there is Given a range [low, high] (both comprehensive), select N numbers from that extend (a number can be picked more than multiple times) with the end goal that total of those N numbers is even.

Presently Piyush needs to locate the quantity of every single such stage. Help Piyush to take care of the issue.

As in light of the fact that this number can be huge, print it in modulo (1e9 +7).

Requirements

0 <= low <= high <= 10^9

N <= 10^6.

Info Format

First line of the information contains two space isolated numbers alluding low and high respectivel

Second line of the information contains a solitary number N.

Yield Format

Print a solitary whole number signifying the quantity of every such stage.

Test Testcase #0

Testcase Input

4 5

3

Testcase Output

4

Clarification

There are 4 legitimate changes viz. {4, 4, 4}, {4, 5, 5}, {5, 4, 5} and {5, 5, 4} which summarize to a much number

Test Testcase #1

Testcase Input

1 10

2

Testcase Output

50

Clarification

There are 50 legitimate changes viz. {1,1}, {1, 3},.. {1, 9} {2,2}, {2, 4},… {2, 10} . . . {10, 2}, {10, 4},… {10, 10}. These 50 changes, each summarize to a much number.