### 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 =

*, i.e.*

**O(T*1)***, where*

**O(T)****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