Just for fun, try to make sense of the following situation. You've uploaded a CGI script written in Perl to your webserver; however, instead of doing anything useful, it only throws a 500 Internal Server Error at you, and your error_log only says "Premature end of script headers".
Script permissions are fine, so you try to work out where the problem is, and eventually end up with the following test script:
#!/usr/bin/perl use CGI qw(:standard); print header(), "Hello world!";
...which still gives the above result. So you decide to ssh into the webserver and see if that one's configuration is weird or different from yours somehow in a way that would cause an otherwise unremarkable and obviously correct script to fail:
$ perl test.pl Content-Type: text/html; charset=ISO-8859-1 Hello world! $
...huh. It's working just fine, and it does output headers and everything, so why isn't working as a CGI script? Your webhoster's Apache installation can be assumed to be in working order, BTW, given that they're a large commercial hoster.
$ ./test.pl zsh: ./test.pl: bad interpreter: /usr/bin/perl^M: no such file or directory $
AHA! You happened to edited this script on a windows box, and while Perl itself ignores the hashbang line when interpreting the script, the shell obviously does not. Apparently, neither does Apache, and your (S)FTP client was not in a mood to perform line end conversion on a text file it transferred, either.