Precomputation

🤓☝️ The GIST If your code is performance-sensitive but relies on an algorithm that is slow for repeated queries. If space isn’t a problem, then precomputation can help!

Precomputation is the technique of computing and storing results in advance so that future queries can be answered quickly. Instead of recalculating expensive operations multiple times, you look them up from a precomputed table, reducing overall runtime.

Key points:

  • Useful when the same calculation is needed repeatedly.
  • Trades space for time: extra memory is used to save computation.
  • Often combined with techniques like memoization or lookup tables.

🤓☝️ Precomputation in the Game Industry Graphics are written in the language of linear algebra, and in most cases we end up using one—or all—of the trigonometric functions ($\sin, \cos, \tan$) very frequently. Computing these functions at runtime can be a real 🍑! To speed things up, games often precompute a lookup table and fetch values from it when needed. A classic example is Quake III Arena (GitHub Repository) which uses a $\sin$ table with 1024 precomputed values. They even optimize further by deriving the other trigonometric functions from the same $\sin$ table using standard identities!

Problem Set for Algorithm Optimization with Precomputation

You are Luc Cloudsurfer, tasked by the U.S. Government to simulate your mortal enemy’s power to aid in her defeat.

Your nemesis, Empress Patina, ruler of the ancient land of Tatto’h, wields the mysterious energy of the Jeddy.
Her power allows her to summon a force field whose strength is determined by:

\[a^n\]

However, her aging body limits how quickly she can manifest her energy:

  • If $a < n < 200$, she can create a force field instantly.
  • If $200 \leq a < n$, the field must be built up through recursive concentration of energy, taking logarithmic time.

Your mission is to simulate the creation of this force field by computing $a^n$ using the same time constraints as Empress Patina.
Since mortals cannot contain infinite energy, the final result must be taken $\bmod 10^9 + 7$.

Input

  • The first line contains an integer $s$, the number of simulations to perform.
  • Each of the next $s$ lines contains two integers $a$ and $n$.

Output

  • Output $s$ lines, each containing a single integer:
\[R = a^n \bmod (10^9 + 7)\]

Constraints

  • $1 \leq s \leq 10^5$
  • $0 < a < 10^8$
  • $0 < n < 10^8$

Example 1 Input:

3
2 10
3 150
5 300

Output:

1024
3486784401
226732710

AI Use Declaration. See AI Use Declaration