As stated you must use the key on the COA sticker to activate a reinstall with the 64 bit installer. That said, I have been able to get MS to activate in the past using the Product Key audited from the HD by Belarc Advisor.
Since Recovery and Tools won't work after clean reinstall, I would Delete all partitions with the booted installer and create new ones. Follow the tips given here to get a perfect reinstall of factory OEM: Reinstalling Windows 7
With HP you can even extract favorite preinstalled apps from the Recovery Disks using this method, so make your Recovery disks just in case: Extract HP 3rd Party Software from RecovCD