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 .
The first line contains integers .
The second line contains integers .
Output a single integer, the sum of weights of all valid arrays modulo .
5 1 1 2 1
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 can be found here.
For all test cases, , , .