Let N be the sum of all prime powers that can be written as 4^n+n^4 for some positive integer n.

What are the last 3 digits of N?

Details and assumptions:
A prime power is a number of the form pk, where p is a prime and k is a positive integer. Examples: 3,9,16.