## NOIP '21 P2 - Sequence

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

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 .