We report the detection of ADFS-27, a dusty, starbursting major merger at a redshift of z=5.655, using the Atacama Large Millimeter/submillimeter Array (ALMA). ADFS-27 was selected from Herschel/SPIRE and APEX/LABOCA data as an extremely red 870 micron riser (i.e., S_250<S_350<S_500<S_870), demonstrating the utility of this technique to identify some of the highest-redshift dusty galaxies. A scan of the 3mm atmospheric window with ALMA yields detections of CO(5-4) and CO(6-5) emission, and a tentative detection of H2O(211-202) emission, which provides an unambiguous redshift measurement. The strength of the CO lines implies a large molecular gas reservoir with a mass of M_gas=2.5x10^11(alpha_CO/0.8)(0.39/r_51) Msun, sufficient to maintain its ~2400 Msun/yr starburst for at least ~100 Myr. The 870 micron dust continuum emission is resolved into two components, 1.8 and 2.1 kpc in diameter, separated by 9.0 kpc, with comparable dust luminosities, suggesting an ongoing major merger. The infrared luminosity of L_IR~=2.4x10^13Lsun implies that this system represents a binary hyper-luminous infrared galaxy, the most distant of its kind presently known. This also implies star formation rate surface densities of Sigma_SFR=730 and 750Msun/yr/kpc2, consistent with a binary maximum starburst. The discovery of this rare system is consistent with a significantly higher space density than previously thought for the most luminous dusty starbursts within the first billion years of cosmic time, easing tensions regarding the space densities of z~6 quasars and massive quiescent galaxies at z>~3.