TopCoder Statistics - Problem Statement

Problem Statement

This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.

There are m positive integer variables: x₁, x₂, ..., x_m. We do not know their exact values, we only know some inequalities they satisfy:

The sum of all our variables is at most s. Formally: x₁ + x₂ + ... + x_m <= s.
Each of the first n variables is less than or equal to t. Formally: for each i such that 1 <= i <= n we have x_i <= t.

You are given the long s and the ints t, n, and m. Compute and return the number of solutions to the above inequalities, modulo 1,000,000,007.

Definition

Class:: TrickyInequality
Method:: countSolutions
Parameters:: long, int, int, int
Returns:: int
Method signature:: int countSolutions(long s, int t, int n, int m)
(be sure your method is public)

Constraints

m will be between 1 and 10^9, inclusive.
n will be between max(1,m-100) and m, inclusive.
t will be between 1 and 10^5, inclusive.
s will be between n*t and 10^18, inclusive.

Examples

3

1

1

2

Returns: 2

In this test case we have two variables, and we know that their sum is at most 3 and that the first variable is at most 1. Formally, we have x1 + x2 <= 3 and x1 <= 1. There are only two solutions in positive integers: (1,1) and (1,2).
5

2

2

3

Returns: 8

Here we are given the following inequalities: x1 + x2 + x3 <= 5 x1 <= 2 x2 <= 2 There are 8 solutions: (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (2,1,1), (2,1,2) and (2,2,1).
30

1

1

10

Returns: 10015005

From the constraints we know that x1 must be 1. Therefore the sum of the nine positive integers x2 through x10 has to be at most 29. It's not hard to find that the answer is the binomial coefficient C(29,9) = 10015005.
2000

20

100

200

Returns: 35422605
999999999999999999

100000

999999900

1000000000

Returns: 90919453
105721

64

33

37

Returns: 754903408
199606

86

9

77

Returns: 168458140
136390

46

36

58

Returns: 119923226
55652

55

71

85

Returns: 626482586
145629

70

31

60

Returns: 578609714
80895

51

22

46

Returns: 618063228
119027

51

42

89

Returns: 619580162
179253

60

3

86

Returns: 862177304
936353860

2567

4080

4128

Returns: 994409629
499262409

2921

7366

7455

Returns: 954667004
821866211

1855

6374

6406

Returns: 701421003
542338886

1799

6290

6315

Returns: 90129548
212290927

1974

5152

5193

Returns: 646281596
927503294

2728

6947

6974

Returns: 310873199
562509916

1251

3390

3392

Returns: 867963158
445405970

1381

5327

5338

Returns: 457279940
822443751041689486

89990

840084932

840085005

Returns: 582496398
739208549591790864

45308

881683449

881683453

Returns: 568281006
537236399226899931

35861

612961921

612961978

Returns: 670452216
314476328358855739

63810

938081821

938081863

Returns: 601268500
603481587169811383

82514

455427928

455427965

Returns: 567654130
183168589723451860

80659

950992302

950992313

Returns: 367813229
850655409765034582

81209

754094342

754094428

Returns: 501637702
10411406421488205

43074

345576398

345576469

Returns: 782878466
884057837920698216

92759

949625116

949625216

Returns: 693753718
407682383075488511

91264

902815697

902815796

Returns: 533583724
78765808655104121

94182

927929972

927930068

Returns: 727041581
374154320325198739

98263

953078799

953078894

Returns: 61260449
289111266817153309

91435

990097892

990097986

Returns: 887060752
801935492095650470

90467

933140054

933140150

Returns: 23667027
999999999999999999

100000

1000000000

1000000000

Returns: 297793005
801935492095650470

90467

933140150

933140150

Returns: 106285029

Statistics

Problem Statement for "TrickyInequality"

Problem Statement

Definition

Constraints

Examples