We report the discovery of a surprising binary configuration of the double-mode Cepheid OGLE-LMC-CEP-1347 pulsating in the first (P-1= 0.690 days) and second-overtone (P-2= 0.556 days) modes. The orbital period (P-orb= 59 days) of the system is five times shorter than the shortest known to date (310 days) for a binary Cepheid. The Cepheid itself is also the shortest-period one ever found in a binary system and the first double-mode Cepheid in a spectroscopically double-lined binary. OGLE-LMC-CEP-1347 is most probably on its first crossing through the instability strip, as inferred from both its short period and fast period increase, consistent with evolutionary models, and from the short orbital period (not expected for binary Cepheids whose components have passed through the red giant phase). Our evolutionary analysis yielded a first-crossing Cepheid with a mass in a range of 2.9-3.4 M-circle dot (lower than any measured Cepheid mass), consistent with observations. The companion is a stable star, at least two times fainter and less massive than the Cepheid (preliminary mass ratio q= 0.55), while also redder and thus at the subgiant or more advanced evolutionary stage. To match these characteristics, the Cepheid has to be a product of binary interaction, most likely a merger of two less massive stars, which makes it the second known classical Cepheid of binary origin. Moreover, further evolution of the components may lead to another binary interaction.