bulbs light bulbs, each painted one of colors colours (numbered from 1 to colors). Two colourings are different if at least one bulb is painted differently.
How many colourings have exactly repeats pairs of adjacent bulbs sharing the same colour?
The answer can be huge, so return it modulo 10⁹ + 7. If that many matches is impossible, the answer is 0.bulbs=3, colors=3, repeats=1 → 12
The matching pair is either the first two bulbs or the last two. Its colour can be chosen in 3 ways and the remaining bulb in 2 (it must differ from its neighbour): 2 · 3 · 2 = 12.
bulbs=4, colors=2, repeats=0 → 2
Neighbours always differ, so the colours alternate: 1, 2, 1, 2 or 2, 1, 2, 1.
bulbs=3, colors=4, repeats=3 → 0
A garland of three bulbs has only two pairs of neighbours, so three matches are impossible.
bulbs=3, colors=3, repeats=1
12
Run checks the first 3 tests in your browser. Submit checks all 4 tests on the server, hidden ones included.