Sachverhalt: Sachverhalt: A. Die 1985 gegründete M._ AG war der Ausgleichskasse des Kantons St. Gallen (nachfolgend: Ausgleichskasse) als beitragspflichtige Arbeitgeberin angeschlossen. S._ war von 1990 bis 7. Mai 1999 als Verwaltungsratspräsident mit Kollektivunterschrift zu zweien, E._ während dieser Zeit als Delegierter des Verwaltungsrats mit Einzelunterschrift, danach als einziges Verwaltungsratsmitglied im Handelsregister eingetragen. Im Juni 2001 wurde die Firma in B._ AG umgeändert und am 13. Juli 2001 über die Gesellschaft der Konkurs eröffnet. Mit Verfügungen vom 13. September 2002 verpflichtete die Ausgleichskasse die beiden Organe zur Leistung von Schadenersatz gemäss Art. 52 AHVG für entgangene Sozialversicherungsbeiträge (einschliesslich Verwaltungskostenbeiträge, Verzugszinsen, Mahngebühren und Betreibungskosten) in solidarischer Haftbarkeit in unterschiedlicher Höhe: E._ zu Fr. 550'951.80 (bundesrechtlicher Teil Fr. 541'856.35, kantonalrechtlicher Teil Fr. 9'095.45) und S._ zu Fr. 74'406.85 (bundesrechtlicher Teil Fr. 69'583.10, kantonalrechtlicher Teil Fr. 4'823.75). Dagegen erhoben beide Betroffenen Einspruch. Mit Verfügungen vom 13. September 2002 verpflichtete die Ausgleichskasse die beiden Organe zur Leistung von Schadenersatz gemäss Art. 52 AHVG für entgangene Sozialversicherungsbeiträge (einschliesslich Verwaltungskostenbeiträge, Verzugszinsen, Mahngebühren und Betreibungskosten) in solidarischer Haftbarkeit in unterschiedlicher Höhe: E._ zu Fr. 550'951.80 (bundesrechtlicher Teil Fr. 541'856.35, kantonalrechtlicher Teil Fr. 9'095.45) und S._ zu Fr. 74'406.85 (bundesrechtlicher Teil Fr. 69'583.10, kantonalrechtlicher Teil Fr. 4'823.75). Dagegen erhoben beide Betroffenen Einspruch. B. Mit Entscheid vom 26. September 2003 hiess das Versicherungsgericht des Kantons St. Gallen die von der Ausgleichskasse erhobene Klage im verfügten Umfang gegen E._ vollumfänglich gut und entschied, S._ hafte bis zum bundesrechtlichen Betrag von Fr. 62'314.75 und bis zum kantonalrechtlichen Betrag von Fr. 4'086.65 solidarisch. Die ebenfalls im verfügten Umfang erhobene Klage gegen S._ hiess es mit demselben Entscheid in reduziertem Umfang von Fr. 66'401.40 (bundesrechtlicher Teil Fr. 62'314.75, kantonalrechtlicher Teil Fr. 4'086.65) teilweise gut, mit solidarischer Haftbarkeit von E._ für diesen Betrag. B. Mit Entscheid vom 26. September 2003 hiess das Versicherungsgericht des Kantons St. Gallen die von der Ausgleichskasse erhobene Klage im verfügten Umfang gegen E._ vollumfänglich gut und entschied, S._ hafte bis zum bundesrechtlichen Betrag von Fr. 62'314.75 und bis zum kantonalrechtlichen Betrag von Fr. 4'086.65 solidarisch. Die ebenfalls im verfügten Umfang erhobene Klage gegen S._ hiess es mit demselben Entscheid in reduziertem Umfang von Fr. 66'401.40 (bundesrechtlicher Teil Fr. 62'314.75, kantonalrechtlicher Teil Fr. 4'086.65) teilweise gut, mit solidarischer Haftbarkeit von E._ für diesen Betrag. C. Mit Verwaltungsgerichtsbeschwerde beantragt S._, der angefochtene Entscheid sei aufzuheben, soweit er bezüglich des bundesrechtlichen Teils solidarisch haftbar erklärt und zu einer Zahlung verpflichtet werde; eventualiter sei die Sache zur Durchführung des Beweisverfahrens und zur Neubeurteilung an die Vorinstanz zurückzuweisen. Während die Ausgleichskasse auf Abweisung der Verwaltungsgerichtsbeschwerde schliesst, verzichtet das Bundesamt für Sozialversicherung (BSV) auf eine Vernehmlassung. Der als Mitinteressierter beigeladene E._ lässt sich ebenfalls nicht vernehmen. Während die Ausgleichskasse auf Abweisung der Verwaltungsgerichtsbeschwerde schliesst, verzichtet das Bundesamt für Sozialversicherung (BSV) auf eine Vernehmlassung. Der als Mitinteressierter beigeladene E._ lässt sich ebenfalls nicht vernehmen. D. Am 29. Januar 2004 reichte S._ zudem eine Vereinbarung zwischen der Ausgleichskasse und E._ betreffend Tilgung der Schadenersatzforderung ein.