Don't ever contact them first!!! you'll be admitting that you are knowingly infringing on their patent, which will put you in an awful position if they decide to pursue litigation. consult a lawyer before you do anything, and have him/her review everything you write to them.

Sorry about the exclamation marks but this is a really dangerous suggestion.