SemiMultiple | Topcoder Archive

Problem Statement

You are given two ints: N and M.

In this problem we will consider N-bit integers. These are nonnegative integers that have at most N bits when expressed in base 2. We will allow leading zeros and treat each such integer as a sequence of exactly N bits.

An N-bit integer is called a semi-multiple of M if it satisfies the following conditions:

It is not a multiple of M.
We can change it into a multiple of M by flipping one of its N bits.

Count all N-bit integers that are semi-multiples of M. Return this count modulo 1,000,000,007.

Definition

Class:: SemiMultiple
Method:: count
Parameters:: int, int
Returns:: int
Method signature:: int count(int N, int M)
(be sure your method is public)

Constraints

N will be between 1 and 2000, inclusive.
M will be between 1 and 2000, inclusive.

Examples

```
3
```
```
3
```
```
Returns: 4
```
In this case, the N-bit integers are the numbers 0 through 7. Numbers 0, 3, and 6 are multiples of M. Numbers 1, 2, 4, and 7 are semi-multiples of M. For example, 4 written in base 2 is "100" and we can change this either to "000" or to "110" by flipping a single bit. Number 5 is not a semi-multiple of M. Flipping a single bit from "101" produces "001", "111", or "100", and neither of these numbers is divisible by M.
```
2000
```
```
1
```
```
Returns: 0
```
Here, all N-bit integers are multiples of M.
```
5
```
```
2
```
```
Returns: 16
```
Only the least significant bit matters. All odd numbers are semi-multiples of M.
```
4
```
```
6
```
```
Returns: 7
```
```
3
```
```
7
```
```
Returns: 6
```
```
2000
```
```
1999
```
```
Returns: 56743750
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.