H. It's showtime
*special
You are given a mysterious language (codenamed ""UnknownX"") available in ""Custom Test"" tab. Find out what this language is, and use it to solve the following problem.You are given an integer \(input = 1000 * n + mod\) (\(1 \le n, mod \le 999\)). Calculate double factorial of \(n\) modulo \(mod\).
The input contains a single integer \(input\) (\(1001 \le input \le 999999\)). You are guaranteed that \(input \mod 1000 \neq 0\).
Output a single number.
In the first test case you need to calculate \(6!! \mod 100\); \(6!! = 6 * 4 * 2 = 48\).In the second test case you need to calculate \(9!! \mod 900\); \(9!! = 9 * 7 * 5 * 3 = 945\).In the third test case you need to calculate \(100!! \mod 2\); you can notice that \(100!!\) is a multiple of 100 and thus is divisible by 2.