Cgi can be really picky about permissions and syntax, and when it isn't exactly perfectly right it throws the very unhelpful 500 error. Step one on troubleshooting is to make sure your cgi-bin directory and cgi file both have 755 permissions. Step two is to make sure you're using the right shebang, which according to your code above looks right to me. Step three is to make sure you set the correct content type.
print "Content-type:text/html\r\n\r\n";
Is what I use for perl cgi and it works on Heliohost. There may be other slight variations that work too. Let us know if that doesn't fix the problem.