Hola
No estoy seguro de a que te refieres con "la primera expresión".
Es claro que trabajando módulo \( 1373 \):
\( 2004\equiv{}631 \)
Por otra parte como \( 1373 \) es primo, por el pequeño teorema de Fermat:
\( a^{1373-1}\equiv 1 \) para cualquier \( a\not\equiv 1373 \)
Por tanto:
\( 2004^{16949687}\equiv 631^{16949687}\equiv 631^{12353\cdot 1372+1371}\equiv 631^{1371}\equiv 631^{-1} \)
Tu problema se reduce a calcular el inverso de \( 631 \) módulo \( 1373 \). Equivalentemente a resolver esta ecuación:
\( 631x\equiv 1\mbox{ mod }1373 \)
y a su vez a resolver esta ecuación diofántica:
\( 631x+1373k=1 \)
Para esto último puedes usar el
algoritmo extendido de euclides.
Saludos.