A CGI script must begin with a valid 'interpreter line' also called 'shebang'. That must be the first line in the file and must start in the first column. It should begin with the two characters '#!', followed by a path to an interpreter, followed by any options.

For example:

#!/usr/bin/php
will run the script through the PHP interpreter at /usr/bin/php.
#!/usr/bin/perl -w
runs the script through /usr/bin/perl with the -w flag to enable warnings.
An 'exec format error' is the result of an invalid interpreter line. That could be because the interpreter line is missing, or indented with a tab, for instance.