Even Odd Codevita 9 Solution

by

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)

Codevita Season 9 All Questions Solution

Leave a Comment

twelve − six =