{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nFancy is learning mathematics recently. He\u0027s already mastered the use of multiplication and addition days before, so today he\u0027s going to learn prime number.\n\u003c/p\u003e\n\u003cp\u003e\nAfter reading the learning material, he\u0027s been asked to complete a simple test. He\u0027s been given an integer \u003cvar\u003eX\u003c/var\u003e larger than 1, using multiplication, addition and at most 3 prime numbers, how many ways could he get the answer as \u003cvar\u003eX\u003c/var\u003e exactly?\n\u003c/p\u003e\n\u003cp\u003e\nSince that Fancy is a new learner of mathematics, he\u0027s still not familiar with brackets. So in the calculation, the addition is always performed after multiplication.\n\u003c/p\u003e\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003e\nThere will be multiple test cases. Each test case contains a single integer \u003cvar\u003eX\u003c/var\u003e (1 \u0026lt; \u003cvar\u003eX\u003c/var\u003e ≤ 80000) in one line.\n\u003c/p\u003e\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003e\nFor each test case, please calculate the number of ways which Fancy could get the answer as \u003cvar\u003eX\u003c/var\u003e. Since that the number of ways might be large, please output it modulo 1000000007.\n\u003c/p\u003e\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n10\n8\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003e\nIn the 3rd case, 8 \u003d 2 * 2 * 2 \u003d 2 + 2 * 3 \u003d 2 + 3 + 3 \u003d 3 + 5, so the answer is 4.\n\u003c/p\u003e\n"}}]}