P15569 [COCI 2025/2026 #5] Structure / Struktura

The full score for this problem is $110$.

Petar and Ivana felt bored on a long winter afternoon, so they invented a number game. Petar randomly writes down $n$ numbers on paper. Each number is chosen **independently and uniformly** from $1$ to $k$, forming an array $a$. Ivana says she especially likes some arrays because they have a kind of “hidden balance”. She calls such arrays **structures (structure)**. The array $a$ is a structure if and only if the following conditions are satisfied: - The integers $1,2,\dots,n$ each appear in the array exactly once. - For every index $i$ ($1 \le i \le n$), we have $|a_i + i - n - 1| \le 1$. Ivana wants to know: when Petar generates the array $a$ completely at random, what is the probability that it is a structure. It can be proven that the answer can always be written as a fraction $\dfrac{P}{Q}$, where $P$ is an integer, and $Q$ is a positive integer that is not divisible by $10^9+7$.

One line contains two non-negative integers $n,k$ ($1 \le n,k \le 10^9$).

Output one integer, representing the required probability modulo $10^9+7$.

#### Sample Explanation Explanation for Sample #2: There are $2^2=4$ possible arrays Petar can write: $(1,1),(1,2),(2,1),(2,2)$. Among them, the structures are $(1,2)$ and $(2,1)$. The probability is $\dfrac{2}{4}$, so the output is $2 \cdot 4^{-1} \bmod (10^9+7)=500000004$. #### Subtasks | Subtask | Score | Limits | | :----: | :--: | :--: | | $1$ | $17$ | $n,k \le 7$ | | $2$ | $23$ | $n \le 7$, $k \le 100$ | | $3$ | $19$ | $n \le 20$, $k \le 100$ | | $4$ | $25$ | $n,k \le 10^6$ | | $5$ | $26$ | No additional limits | Translated by ChatGPT 5