TopCoder Statistics - Problem Statement

Problem Statement

Hero likes some arrays. The arrays he likes are the arrays that have all of the following properties:

The length of the array is n.
Each element is an integer between 1 and k, inclusive.
Whenever A and B are two consecutive elements of the array (in this order), we have (A <= B) or (A mod B != 0).

For example, suppose n=4 and k=7. Hero will like the array {1,7,7,2} because it has the right length, all elements are in the correct range, 1 <= 7, 7 <= 7, and 7 mod 2 != 0. Hero will not like the array {4,4,4,2}.

You are given the ints n and k. Let X be the number of different arrays Hero likes. Compute and return the value (X mod 1,000,000,007).

Definition

Class:: DivFree
Method:: dfcount
Parameters:: int, int
Returns:: int
Method signature:: int dfcount(int n, int k)
(be sure your method is public)

Constraints

n will be between 1 and 50,000, inclusive.
k will be between 1 and 50,000, inclusive.

Examples

2

2

Returns: 3

The three arrays Hero likes are {1,1}, {1,2}, and {2,2}.
3

2

Returns: 4

The four arrays Hero likes in this case are {1,1,1}, {1,1,2}, {1,2,2}, and {2,2,2}.
3

3

Returns: 15
1

107

Returns: 107
5

6

Returns: 2292
42

23

Returns: 301026516
37895

31830

Returns: 17278449
35584

32944

Returns: 645600769
32228

29184

Returns: 547595929
977

16330

Returns: 628237713
40610

27203

Returns: 488458572
7687

14516

Returns: 738653668
26970

39831

Returns: 401363280
11671

34303

Returns: 639094965
604

2092

Returns: 677386170
30119

1

Returns: 1
20148

7309

Returns: 775335732
49532

47240

Returns: 892487606
32994

50000

Returns: 999420142
10774

26497

Returns: 705399218
1

40

Returns: 40
3635

11768

Returns: 825126374
35614

28345

Returns: 651309097
17972

14502

Returns: 299625359
15075

39083

Returns: 94500395
13866

48326

Returns: 918224240
18135

20402

Returns: 454253399
5629

43443

Returns: 838554720
6723

50000

Returns: 789120918
39077

48508

Returns: 860559314
22131

27290

Returns: 500998865
21741

7446

Returns: 408698039
23130

11282

Returns: 378550893
33153

22424

Returns: 876679078
1

28563

Returns: 28563
35049

34307

Returns: 767914787
15807

9901

Returns: 425673264
1029

37798

Returns: 415298563
46375

27904

Returns: 745096971
13269

17193

Returns: 999789418
16941

74

Returns: 296027769
9855

42013

Returns: 794637623
11184

50000

Returns: 21647015
24665

19437

Returns: 481037441
1

28347

Returns: 28347
6615

45193

Returns: 755341472
8638

8108

Returns: 723720597
16181

14952

Returns: 945390733
9846

5119

Returns: 258495167
1

38621

Returns: 38621
17163

28190

Returns: 468695835
17985

6582

Returns: 154509155
13511

1048

Returns: 621554832
12246

34062

Returns: 274258923
18185

37223

Returns: 429388972
45918

47111

Returns: 974125928
24772

32215

Returns: 50826269
47078

21327

Returns: 195995612
47943

44943

Returns: 306355554
31491

41243

Returns: 618063334
23072

2993

Returns: 969459559
17774

41169

Returns: 794379927
24817

14354

Returns: 632240272
27994

39059

Returns: 93477117
36461

2037

Returns: 430789025
10857

15255

Returns: 192753573
2677

41876

Returns: 478252473
6537

16756

Returns: 496347323
25095

50000

Returns: 497260706
21966

11122

Returns: 462300084
42745

49266

Returns: 645145374
22909

29682

Returns: 362388003
637

1

Returns: 1
20600

19534

Returns: 689479946
5700

87

Returns: 194345810
4123

36544

Returns: 312171439
4847

44706

Returns: 379100986
20793

27152

Returns: 23165410
27469

29682

Returns: 695813134
3422

6678

Returns: 726098430
28251

1707

Returns: 139222037
32937

27851

Returns: 285368735
9536

40436

Returns: 703334811
10821

13911

Returns: 118380129
23617

40894

Returns: 690961933
37430

47138

Returns: 176629878
45014

5354

Returns: 833672096
37511

21757

Returns: 473048480
46755

46069

Returns: 143778911
13581

14794

Returns: 991816377
14530

17507

Returns: 161905035
23459

32858

Returns: 576257986
42319

46149

Returns: 230835966
27008

3095

Returns: 231293002
6344

38215

Returns: 416150548
44789

42855

Returns: 351835457
35383

6082

Returns: 538049375
21169

36520

Returns: 809931223
30527

2021

Returns: 851648046
27720

25094

Returns: 671286195
7598

10812

Returns: 275574591
19652

29112

Returns: 841267214
6542

25824

Returns: 349412714
8941

35893

Returns: 216253016
30790

7854

Returns: 384693557
39339

37567

Returns: 206587913
814

15473

Returns: 51153422
23348

7305

Returns: 402359951
33987

43696

Returns: 31225490
49998

50000

Returns: 309622312
32245

4768

Returns: 838788454
37730

4148

Returns: 776734597
18098

47559

Returns: 469826520
484

16797

Returns: 811214075
15029

13226

Returns: 64539586
43314

25931

Returns: 282282944
34421

14105

Returns: 994443812
43617

14248

Returns: 391070866
21426

7381

Returns: 609246403
40319

28292

Returns: 249988423
7838

26716

Returns: 167118585
28181

22755

Returns: 230276300
33957

46632

Returns: 653296417
16470

49998

Returns: 744224705
1726

9351

Returns: 565291975
24813

111

Returns: 559794323
50000

50000

Returns: 541697486
49987

49729

Returns: 811020076

Statistics

Problem Statement for "DivFree"

Problem Statement

Definition

Constraints

Examples