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

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.

Subscribe to our newsletter!

[newsletter_form type=”minimal” lists=”undefined” button_color=”undefined”]

1 COMMENT

LEAVE A REPLY

Please enter your comment!
Please enter your name here

13 + 11 =

Most Popular

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...

Recent Comments