Double Increasing Series

Asked in:
Accenture

Problem Description

Given two integers A and B.
Find the number of sequences of length B, such that every element of this sequence is an positive integer and is less than of equal to A, also every previous element in the sequence is less than or equal to half of the next element.

Problem Constraints

1 <= A <= 10⁵
1 <= B <= 20

Input Format

Given two integers A and B.

Output Format

Return an integer, the number of possible sequences modulo 10⁹+7.

Example Input

Input 1:

A = 4, B = 2

Input 2:

A = 4, B = 3

Example Output

Output 1:

Output 2:

Example Explanation

Explanation 1:

The possible sequences are {1, 2}, {1, 3}, {1, 4}, {2, 4}.

Explanation 2:

The only possible sequence is {1, 2, 4}.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Double Increasing Series on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Asked In:

Accenture

Double Increasing Series

Discussion