Home Programming CodeVita Even Odd Solution

# Even Odd Solution [Codevita 9]

## Even Odd

### Problem Description

In this even odd problem 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

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.

### 5 Best Wireless Neckband under Rs. 2000 – October 2020

If you are looking for Best Wireless Neckband under 2000, then you are at right place. We have covered all best neckbands...

### 15 Best Easiest Programming Languages in the World in 2020

A programming language in today’s generation can really ace up one’s skill set and benefit you in the long run. Having said...

### Carl Pei – “Thank You OnePlus”

Just with a simple "Thank You" message , Carl Pei on Friday left OnePlus. He was the Man behind the Success of...

### What is cloud computing? Introduction to Cloud Computing

In this article we will talk about one of the most trending and important technologies, which is playing a pivotal in our...