[warut]

ผมก็ไม่ทราบเหมือนกันว่าวิธีไหนเหมาะสมกับข้อ 16 ที่สุด แต่วิธีที่ผมทำน่าจะมีเลขที่
ต้องคิดน้อยกว่าของคุณ gon นะครับ เพียงแต่ต้องทราบ Euler-Fermat Theorem
เท่านั้น (สำหรับคนที่ได้ผ่านเข้ารอบไปฝึกวิชากับเหล่าเทพเจ้า คงจะต้องได้เรียนแน่ครับ)

ทฤษฎีนี้กล่าวว่า ถ้า gcd(a, m) = 1 แล้ว a^f(m) บ 1 (mod m) โดยที่ f คือ Euler's phi function

เริ่มจากพิจารณาใน modulo 125 ก่อนนะครับ เพราะ 1000 = 2³5³ = 8*125
เนื่องจาก f(5³) = 5²f(5) = 25*4 = 100 ดังนั้น 2¹⁰⁰ บ 1 (mod 125)
เราจึงสนใจว่า 2²⁰⁰⁴ บ ? (mod 100)
แต่เรารู้ว่า f(5²) = 5f(5) = 20 ดังนั้น 2²⁰ บ 1 (mod 25)
เพราะฉะนั้น 2²⁰⁰⁴ บ 2⁴ = 16 (mod 25) นั่นคือ 25 | 2²⁰⁰⁴ - 16
แต่เรารู้ว่า 4 | 2²⁰⁰⁴ - 16 ด้วย ดังนั้น 100 | 2²⁰⁰⁴- 16 นั่นคือ 2²⁰⁰⁴ บ 16 (mod 100)
และ 2²⁰⁰⁴ - 3 บ 13 (mod 100) (ทำไมถึงมี -3 เดี๋ยวก็จะเข้าใจครับ)
เพราะฉะนั้น 2^{2^2004 - 3} บ 2¹³ = 8192 บ 67 (mod 125) นั่นคือ 125 | 2^{2^2004 - 3} - 67
ดังนั้น 1000 หาร 8*(2^{2^2004 - 3} - 67) = 2^{2^2004} - 8*67 = 2^{2^2004} - 536 ได้ลงตัว
สรุปเศษของการหารก็คือ 536 ครับ ทำจริงๆน่าจะใช้เวลาน้อยกว่าที่ผมพิมพ์เยอะเลย