### PROBLEM LINK:

**Author:** sahilarora.535

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

None

### PROBLEM:

Given a number **N**, output **(N!)%1589540031**

### EXPLANATION:

Memoize all the factorials till **10^5** before the test cases and store them in an array * Fact*. Then directly print ***Fact(N)***.

Program Complexity = ***O(T*1)***, i.e. ***O(T)***, where

**T**is the number of test case.

### ALTERNATIVE SOLUTION:

There was this alternate solution which could be deciphered by looking at the number **mod**, which was equal to **1589540031 = (3^13)*997**. So basically, even by naive approach, one needed to find the modulo only upto **996!**, because after that, the factorial would be completely divisible by the mod, and hence the answer would be *0*.

Program Complexity = ***O(T*997)***, which would pass in 1 second.

### AUTHORâ€™S SOLUTIONS:

Solution 1(by method 1 - memoization) - here.

Solution 2(by alternative method) - here