Any advice on computing 2^n modulo m for MANY values of m, m is 64-bit, n is <10000 say

[William Galway]

 I've been considering this computation off-and-on for many years, so my
apologies if I'm repeating a previous post.

I'd like to calculate $2^n$ modulo $m$ with $n$ fixed and no more than
32-bits and with $m$ running over many 64-bit values.  The values of $m$
will be odd and in increasing order, could be restricted to  primes, and
the difference between successive values of $m$ will be "small" multiples
of $n$.  As I indicated in the subject-line, $n$ will be fixed as  $m$
varies and then be changed.  "Typical" values might be $n = 2000$, $m <
10^16$, so for that one value of $n$ I'd expect to perform on the rough
order of $10^12$ modular powering operations if I restrict $m$ to prime
values.

The obvious candidate might be mpz_powm_ui(rslt, 2, n, m), with the
arguments cast to the proper types, but surely one could do better with the
arguments restricted to the values I'll use.  I'd be willing to hand-code
the function in assembly language, although my assembly-language skills
have not been exercised for a few decades.  I'd also be willing to let a
computer spend a day or so generating/preprocessing the code for a fixed
$n$ of "moderate" size, say $n < 10^4$.

I expect to run the function on a "recent" Core i7 processor (or perhaps a
"recent" AMD processor).  Currently I'm using a Core i7-6800K.  I've run a
few benchmarks using various methods (like mpz_powm_ui), but I feel that I
could do much better.

So, are there any suggestions as to how I might best do this?  Thanks!

-- Regards, William (Will) Galway