ASP.NET: Setting a cookie in a cached page

Question

How do I set a cookie on a page, base on a query-string-value, if the page is returned by the Output-cache?

I have a page with this output-cache:

<%@ OutputCache VaryByParam="cookievalue" ...

And I have this code in the Global.asax's *Application_BeginRequest*:

// Validation and checkings
HttpCookie cookie = new HttpCookie("__cookievalue");
cookie.Value = Request.QueryString["cookievalue"];
Response.SetCookie(cookie);

The first time I hit a page with Page.aspx?cookievalue=val1 I get the expected result. But then going to Page.aspx?cookievalue=val2 and from there flipping between these two I don't get an updated cookie-value.

It seems that even though I do a Response.SetCookie, the page's Output-cache overrides this and does not execute the response.

Is there a way to work around this?