Base or Bias Codechef solutions Today | Codechef Starters 72 ✅ (100/100) FULL | AC Code ✅| RJBIAS

Problem

Reyaan has given you the following problem to solve:

You are given an integer $K$ in base $B$, represented by an array $A$ of length $N$ such that

• $0 \leq A_i \lt B$ for every $1 \leq i \leq N$
• $\sum_{i=1}^N A_i \cdot B^{N-i} = K$

Note that $N \leq B$ in this problem.

Find the smallest non-negative integer $X$ such that $X+K$ contains every digit from $0$ to $B-1$ in its base-$B$ representation.

$X$ can be very large, so print the answer modulo $10^9 + 7$.

Note: Leading zeros are not counted as part of the number, so for example $12 = 012$ has only two distinct digits: $1$ and $2$. However, $102$ does have three distinct digits.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input.
  • The first line of each test case contains two space-separated integers $N$ and $B$ — the size of the array $A$ and the base.
  • The second line of each test case contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

Output Format

For each test case, output on a new line the value of $X$, modulo $10^9 + 7$.

Constraints

Sample 1:

4
4 4
3 1 0 2
4 5
1 2 3 4
2 2
1 1
1 3
2

0
500
1
9

Explanation:

Test case $1$: All the digits from $0$ to $B-1=3$ are already present in the given array, so $X = 0$.

Test case $2$: In base $5$, $[1, 2, 3, 4]$ represents the integer $194$. The smallest number larger than the given one that contains every digit is $[1, 0, 2, 3, 4]$, which represents $694$. The difference between them is $500$.

Test case $3$: We have $K = 3$, which is $[1, 1]$ in binary. If we add $X = 1$ to it, we obtain $K+X = 4$, which is $[1, 0, 0]$ in binary and has both digits.