Sachverhalt:
A.
Der südafrikanische Staatsangehörige X._ hatte die Schweiz aufgrund einer rechtskräftigen Ausreiseverfügung des Migrationsamts des Kantons Zürich bis zum 31. Oktober 2011 zu verlassen. Er kam dieser nicht nach und hielt sich nach Ablauf der Ausreisefrist weiterhin ununterbrochen in der Schweiz auf.
B.
Das Bezirksgericht Zürich verurteilte X._ am 1. November 2012 wegen Widerhandlung gegen das Ausländergesetz (AuG; SR 142.20) zu einer unbedingten Freiheitsstrafe von 70 Tagen.
X._ legte Berufung ein. Das Obergericht des Kantons Zürich sprach ihn am 7. Mai 2013 vom Vorwurf des rechtswidrigen Aufenthalts frei.
C.
Die Oberstaatsanwaltschaft des Kantons Zürich führt Beschwerde in Strafsachen und beantragt, das angefochtene Urteil sei aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen.

Erwägungen:
1.
1.1. Die Beschwerdeführerin rügt, die Vorinstanz verletze Art. 115 AuG, indem sie den Beschwerdegegner trotz seines illegalen Aufenthalts in der Schweiz freispreche.
1.2. Die Vorinstanz stellt fest, es sei unbestritten, dass sich der Beschwerdegegner vom 1. November 2011 bis zum 6. Juni 2012 ohne gültigen Aufenthaltstitel und damit rechtswidrig in der Schweiz aufhielt (Urteil S. 10). Sie gelangt zum Schluss, seine Behauptung, er habe seinen Reisepass verloren oder könne ihn nicht finden, sei unglaubhaft. Damit gehe sein Vorbringen an der Sache vorbei, wonach er mangels gültiger Reisepapiere nicht legal habe ausreisen können (Urteil S. 15). Das Migrationsamt habe weder im angeklagten Zeitraum noch zuvor Rückführungsmassnahmen ergriffen, obwohl es von der Polizei darüber informiert worden sei, dass sich der Beschwerdegegner weigere, die Schweiz zu verlassen. Es lägen keine Hinweise vor, dass eine zwangsweise Rückführung vergeblich versucht oder unmöglich gewesen wäre. Im verwaltungsrechtlichen Verfahren sei für den Vollzug der Ausreiseverfügung nicht alles Zumutbare unternommen worden, und die Rückkehr sei nicht am Verhalten des Beschwerdegegners gescheitert. Angesichts der bundesgerichtlichen Rechtsprechung könne der Beschwerdegegner nicht wegen rechtswidrigen Aufenthalts verurteilt werden (Urteil S. 17 f.).
1.3. Die Strafrechtliche Abteilung des Bundesgerichts hat sich mit der Anwendung der EU-Rückführungsrichtlinie und dem Verhältnis zur innerstaatlichen Sanktionierbarkeit während des Rückführungsverfahrens befasst. Auf diese grundlegenden Ausführungen kann verwiesen werden (vgl. Urteil 6B_196/2012 vom 24. Januar 2013 E. 2).
1.4. Das Vorbringen der Beschwerdeführerin, die Rückführung sei gescheitert, weil der Beschwerdegegner nicht bereit gewesen sei, bei der Beschaffung von Reisepapieren mitzuwirken, überzeugt nicht. Einerseits weicht sie von den verbindlichen Sachverhaltsfeststellungen der Vorinstanz ab, ohne darzutun, weshalb diese schlechterdings unhaltbar wären (Art. 105 Abs. 1 und 2 BGG). Andererseits widerspricht sie ihrem eigenen Einwand, wonach die Aussagen des Beschwerdegegners zum Verlust seines Reisepasses reine Schutzbehauptungen seien. Im Übrigen verkennt sie, dass er den Verlust des Reisepasses erstmals anlässlich der staatsanwaltschaftlichen Einvernahme vom 6. Juni 2012 geltend machte (vgl. Urteil S. 11 ff.), mithin nach dem angeklagten Zeitraum. Seine Rückführung scheiterte somit nicht an dem angeblich fehlenden Reisepass. Entgegen der Beschwerdeführerin war im Anklagezeitpunkt eine sofortige Ausschaffung des Beschwerdegegners möglich. Die erstinstanzliche unbedingte Freiheitsstrafe von 70 Tagen war damit geeignet, die Rückführung des Beschwerdegegners zu verzögern oder zu verhindern.
Unbegründet ist der Einwand, gestützt auf Art. 115 Abs. 4 AuG könne, selbst wenn der Beschwerdegegner bestraft werde, von einer Strafe abgesehen werden, sobald eine Ausschaffung möglich werde. Gemäss dieser Bestimmung kann von der Strafverfolgung, der Überweisung an das Gericht oder der Bestrafung bei rechtswidrig eingereisten Ausländerinnen und Ausländern absehen werden, sofern sie sofort ausgeschafft werden. Die Voraussetzungen für die Strafbefreiung müssen in dem Zeitpunkt vorliegen, in dem darüber entschieden wird (in der Regel bei Erlass eines Strafbefehls oder Urteils). Es kann nicht darauf zurückgekommen werden, sobald eine Ausschaffung möglich wird.
Die Vorinstanz verletzt kein Bundesrecht, wenn sie den Beschwerdegegner vom Vorwurf des rechtwidrigen Aufenthalts freispricht.
2.
Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Es sind keine Gerichtskosten zu erheben (<ref-law>). Dem Beschwerdegegner ist keine Parteientschädigung auszurichten, da ihm im bundesgerichtlichen Verfahren keine Kosten entstanden sind.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Es werden keine Gerichtskosten erhoben.
3.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 15. August 2014
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Denys
Die Gerichtsschreiberin: Andres