# Even Odd Codevita 9 Solution

## Even Odd Codevita 9 Solution

Given a range [low, high] (both inclusive), select K numbers from the range (a number can be chosen multiple times) such that sum of those K numbers is even. Calculate the number of all such permutations. As this number can be large, print it modulo(1e9+7)

Constraints

• 0<=low<=high<=10^9
• K<=10^6

Input

First line contains two space separated integers denoting low and high respectively Second line contains a single integer K

Output

Print a single integer denoting the number of all such permutations

Time Limit

1

Examples

Example 1

Input
4 5
3

Output
4

Explanation

There are 4 valid permutations viz. {4, 4, 4}, {4, 5, 5}, {5, 4, 5} and {5, 5, 4} which sum up to an even number

Example 2

Input
1 10
2

Output
50

Explanation

There are 50 valid permutations viz. {1,1}, {1, 3},.. {1, 9} {2,2}, {2, 4},â€¦ {2, 10} . . . {10, 2}, {10, 4},â€¦ {10, 10}. These 50 permutations, each sum up to an even number.

### SOLUTION

Program: Even Odd Codevita 9 Solution in Python

``````r1,r2=map(int,input().split())
combo=int(input())
lst=[i for i in range(r1,r2+1)]
a=len(lst)
res=(a**combo)//2
print(res%100000009)``````