Token Spread Over All Layouts

Hard

You have a board with rows rows and cols columns, and tokens identical tokens. A layout is a way to put all the tokens on the board with at most one token per cell. For a single layout, add up the Manhattan distances over every pair of tokens (the distance between cells (r1, c1) and (r2, c2) is |r1 − r2| + |c1 − c2|). Return the sum of that quantity over all possible layouts. The answer can be huge, so return it modulo 10⁹ + 7.

Example 1

rows=1, cols=3, tokens=2 → 4

There are three layouts: tokens in cells 1 and 2 (distance 1), 1 and 3 (distance 2), 2 and 3 (distance 1). In total 1 + 2 + 1 = 4.

Example 2

rows=2, cols=2, tokens=3 → 16

There are 4 ways to occupy three of the four cells. In each one, two pairs of tokens are adjacent (distance 1) and one pair is diagonal (distance 2), giving 4. So the total is 4 · 4 = 16.

Constraints

1 ≤ rows, cols ≤ 10⁵
2 ≤ rows · cols ≤ 10⁵
2 ≤ tokens ≤ rows · cols

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Combinatorics

Similar problems

Tasters and the Spoiled Cask Hard Radio Show Without Quick Repeats Hard Parcel Run Orders Hard A Fair Split of Colored Beads Hard Other Orders for the Same Search Tree Hard

Input

rows=1, cols=3, tokens=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 91 tests on the server, hidden ones included.