Sachverhalt: A. Am 18. Oktober 1998 fuhr B.D._ (Schädiger; materieller Halter des Fahrzeugs) in Basel-Stadt in einem PW Toyota Supra 3.0i Turbo um ca. 01.10 Uhr auf dem Walkeweg in Richtung "Auf dem Wolf". Auf dem Rücksitz des Fahrzeugs fuhr sein jüngerer Bruder, C.D._ (Geschädigter), mit. Beide waren nicht angegurtet. Beim Walkeweg handelt es sich um eine sechs Meter breite, als Einbahnstrasse mit beschränktem Gegenverkehr (BVB-Bus, Rad- und Mofafahrer) signalisierte geteerte Nebenstrasse. Auf dem Walkeweg gilt als Innerortsstrasse die signalisierte Höchstgeschwindigkeit von 50 km/h. An der Unfallstelle weist er ein Gefälle von 7 % auf. Er ist nachts durchgehend künstlich und gut beleuchtet. Die Fahrbahn war nass. Nach dem Befahren der leichten Linkskurve geriet das Fahrzeug aus der Fahrspur und kollidierte seitlich bzw. touchierte rund 55 m vor der Verzweigung "Auf dem Wolf" mit einem ausgangs Kurvenbereich vorschriftswidrig am linken Strassenrand parkierten Lieferwagen. Durch die seitliche Kollision mit dem Lieferwagen wurde das Unfallfahrzeug nach rechts abgetrieben, überquerte den Walkeweg diagonal und überfuhr weiter unten das rechtsseitig gelegene Trottoir. Es durchbrach den hinter dem Trottoir verankerten Maschendrahtzaun und kollidierte mit dem Oberhalb der Grasböschung stehenden Beleuchtungskandelaber. Hernach überwand es die stark abfallende Grasböschung und stürzte in ein Tankstellengelände, wobei es sich überschlug und schliesslich zwischen den Tanksäulen und dem Tankstellenshop auf dem Dach landete. Der Schädigererlag noch auf der Unfallstelle seinen Verletzungen. D ie Suva (Schweizerische Unfallversicherungsanstalt, Klägerin 1, Beschwerdeführerin 1), die Eidgenössische Invalidenversicherung (IV) (Klägerin 2, Beschwerdeführerin 2) und die Schweizerische Alters- und Hinterlassenenversicherung (AHV) (Klägerin 3, Beschwerdeführerin 3) machen geltend, der Geschädigte habe beim Unfall diverse Verletzungen erlitten und sie hätten für ihn Leistungen für Heilungskosten sowie Erwerbsausfallleistungen erbracht und würden solche auch inskünftig erbringen. Für die ausgerichteten und die künftigen Leistungen machen sie ein Regressrecht gegen die Versicherung A._ (Beklagte, Beschwerdegegnerin) geltend, den Haftpflichtversicherer des Schädigers. Sie gehen davon aus, dieser sei angesichts der misslichen Strassenverhältnisse mit übersetzter Geschwindigkeit (mindestens 69 km/h) gefahren. B. Am 28. August 2014 reichten die Klägerinnen beim Handelsgericht des Kantons Zürich Klage ein und beantragten, die Beklagte sei zu verpflichten, ihnen Fr. 2'751.114.65 nebst Zins zu 5 % auf Fr. 2'373'027.20 seit 1. September 2014 zu bezahlen. Eine Neuberechnung der Forderungen nebst Zins per Urteilstag bleibe ausdrücklich vorbehalten. Mit Urteil vom 17. März 2016 wies das Handelsgericht die Klage kostenfällig ab. C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführerinnen dem Bundesgericht, das Urteil des Handelsgerichts sei kostenfällig aufzuheben und die Sache sei zur Fortführung des Forderungsprozesses, insbesondere zur Beweisabnahme und materiellen Beurteilung der Klage an dieses zurückzuweisen. Die Beschwerdegegnerin trägt auf kostenfällige Abweisung der Beschwerde an. Das Handelsgericht hat auf eine Vernehmlassung verzichtet.