You are given 23 whole numbers, not necessarily distinct, in a row.

You cannot change the order of the numbers.

Prove that there exists an arrangement of the symbols ‘+’, ‘×’, ‘(‘ and ‘)’ in-between the 23 numbers, such that the final result is a valid formula, whose evaluated value equals 0 mod 2000.

Extra Credit

1. Is 23 a tight bound? Can you find a sequence of 22 numbers such that all arrangements of the symbols ‘+’, ‘×’, ‘(‘ and ‘)’ in-between them will result in numbers that are different from 0 mod 2000?
2. Consider a more general case. Replace in the riddle above the number 23 by K and the number 2000 by N. Describe all the pairs, K, N, for which a solution to the riddle exists.

Thanks to Misha Seltzer, for sending me this cool riddle!