Problem Statement
You are given two
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
1250
808
Returns: 402180775
1659
74
Returns: 264680748
1273
931
Returns: 465764775
879
1545
Returns: 317720628
1710
1924
Returns: 759862956
166
441
Returns: 806466188
1043
493
Returns: 589799700
504
1988
Returns: 375177984
1730
328
Returns: 981183171
613
841
Returns: 762273138
1170
304
Returns: 982005442
1158
1710
Returns: 90719440
934
1561
Returns: 336869550
279
1100
Returns: 76494192
1336
1817
Returns: 136043237
1827
1098
Returns: 177767068
1268
1513
Returns: 166159813
1634
1811
Returns: 860949573
1150
980
Returns: 70076780
822
580
Returns: 152197493
673
1968
Returns: 486438693
1337
1394
Returns: 926367514
1746
1486
Returns: 821722076
92
1229
Returns: 974998236
358
195
Returns: 188474208
1154
1002
Returns: 514719416
1945
709
Returns: 141437828
1491
1669
Returns: 523923037
197
125
Returns: 247162113
904
1531
Returns: 231458003
667
1723
Returns: 916953596
25
550
Returns: 1403193
854
1802
Returns: 780066916
1409
978
Returns: 44510996
934
229
Returns: 701176697
982
299
Returns: 643751005
14
636
Returns: 364
1815
1866
Returns: 813579213
537
1064
Returns: 728804298
1670
1426
Returns: 490226897
95
116
Returns: 505372768
502
1630
Returns: 806017017
196
518
Returns: 950106881
405
106
Returns: 929713382
299
1452
Returns: 718846778
1124
189
Returns: 802521816
883
1506
Returns: 591651011
1567
753
Returns: 220650905
338
717
Returns: 370334385
1145
439
Returns: 51202339
898
1502
Returns: 174520813
1829
1872
Returns: 859764920
1359
1138
Returns: 300306158
398
1178
Returns: 490460709
1905
295
Returns: 334719914
232
1610
Returns: 469246418
176
1746
Returns: 46454480
299
1636
Returns: 804120235
400
143
Returns: 942461867
413
1969
Returns: 880686124
1558
261
Returns: 923173531
9
1595
Returns: 9
1969
396
Returns: 802740152
531
1114
Returns: 32446564
963
1007
Returns: 970967685
1366
1943
Returns: 823911256
1853
83
Returns: 196946461
1822
768
Returns: 55672065
713
1696
Returns: 277244710
1902
1672
Returns: 496733978
832
591
Returns: 458527701
1058
739
Returns: 423603295
1791
1617
Returns: 393224521
680
1641
Returns: 499070082
1007
1336
Returns: 702478556
99
1973
Returns: 941120404
1320
1096
Returns: 860104328
1224
1455
Returns: 414916075
761
290
Returns: 104743707
127
906
Returns: 770782383
1507
124
Returns: 726692439
771
1814
Returns: 386284853
1095
1239
Returns: 424305493
1845
221
Returns: 842249350
535
367
Returns: 834637913
1395
1227
Returns: 923132165
739
1364
Returns: 775790663
1591
1845
Returns: 277605062
1160
551
Returns: 422204678
948
624
Returns: 105027091
1218
1386
Returns: 195063897
1540
1273
Returns: 852487390
386
1248
Returns: 978143487
886
1497
Returns: 195900497
421
624
Returns: 838047594
1969
145
Returns: 209653884
1916
1736
Returns: 231915196
1535
1626
Returns: 831945782
12
43
Returns: 878
153
680
Returns: 963976959
2000
1
Returns: 0
1
2000
Returns: 1
2000
2000
Returns: 21662864
2000
1024
Returns: 140129088
1803
1024
Returns: 737288083
2000
1890
Returns: 695467257
1
1
Returns: 0
1
2
Returns: 1
1
3
Returns: 1
2000
1997
Returns: 837936004