You are given integers and
positive integers
.
For a one-based array containing
integers between
and
, its weight is defined as
.
Such an array is valid if
contains no more than
ones in its binary representation.
Calculate the sum of weights of all valid arrays . Output the sum modulo
.
Input Specification
The first line contains integers
.
The second line contains integers
.
Output Specification
Output a single integer, the sum of weights of all valid arrays modulo .
Sample Input
5 1 1
2 1
Sample Output
40
Sample 1 Explanation
Because is
and
implies
, there is only one possible
:
. This requires that
contains two
s and three
s. Thus, we have
valid arrays. Each array has weight
. The sum is
.
Additional Samples
Additional samples can be found here.
Constraints
For all test cases, ,
,
.
Test cases | |||
---|---|---|---|
Comments