Oh and I looked at the logs as suggested earlier. Look what we have here:
attempt to invoke directory as script
I figured it out. I had to modify the .Conf file for my virtualhost.
Find the lines that say ScripAlias and replace it with the ones in the code below. I had to do it twice because I have port 443 and 80. Now I want to figure out how to add it to vhost.conf because parallels plesk panel will change my last_httpd.conf when it wants.
Alias /cgi-bin/ /var/www/vhosts/mysite.com/httpdocs/cgi-bin/
<Directory /var/www/vhosts/mysite.com/httpdocs/cgi-bin/>
AddHandler cgi-script .cgi
Options ExecCGI
</Directory>
Works like a champ now.