Practice
Authors: Vidit Jain, Pramod Rao
The bug in this problem is in these lines
ll product = 1;
for (int i = 0; i < n; i++)
product = (product * dp[i]) % MOD;
ll ans = 0;
for (int i = 0; i < n; i++) {
ans = (ans + product * inv(dp[i]) % MOD) % MOD;
}
When there is a single element with the value 0 in the dp array, the product as well as the ans would be 0. However in the correct solution, when we are skipping that index, we should have a non-zero ans.
Hence, the case
1
1000000000 7
would break the buggy code, as the dp array would be [1000000000, 0], hence the code would output 0 although the correct answer is 1000000000.