Magical Menu

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK108/hindi/MGICMENU.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK108/mandarin/MGICMENU.pdf), [Russian](http://www.codechef.com/download/translated/COOK108/russian/MGICMENU.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK108/vietnamese/MGICMENU.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK108/bengali/MGICMENU.pdf) as well. In Chefland, there are $M$ types of cookies, numbered $1$ through $M$. There is an infinite supply of cookies of each type. Each morning, the Master Chef of Chefland prepares a menu — a sequence of cookies. There may be multiple cookies with identical types in a menu. Two menus are considered different if the total number of cookies in one menu is different from their total number in the other menu or there is a valid index $x$ such that the type of the $x$th cookie in one menu is different from the type of the $x$th cookie in the other menu. For example, menus $(1, 2, 1)$, $(1, 2, 1, 2)$ are different, and $(1, 1, 2, 3)$, $(1, 2, 1, 3)$ are also different. To make things interesting, each morning, Master Chef receives three integers $L$, $R$ and $K$. To prepare a menu on that morning, he may use a cookie of type $x$ only if $L \le x \le R$ and he may not use more than $K$ cookies in total in this menu. For example, when $L = 3$, $R = 5$ and $K = 4$, then $(5, 4, 3, 5)$ and $(3, 5, 5)$ are possible menus, while $(5, 4, 3, 5, 4)$ and $(3, 5, 6)$ are not. Moreover, a menu becomes *special* only if there is no integer $x \gt 1$ that divides the type of each cookie in the menu, i.e. a menu $S = (s_1, s_2, \ldots, s_n)$ is special if $\mathrm{gcd}\,(s_1, s_2, \ldots, s_n) = 1$. You should process $Q$ queries. In each query, you are given the parameters $L$, $R$ and $K$ for one morning. Master Chef wonders how many different special menus are possible. Can you help him calculate the number of possible special menus on each morning modulo $2^{30}$? ### Input  The first line of the input contains two spaceseparated integers $M$ and $Q$.  Each of the next $Q$ lines contains three spaceseparated integers $L$, $R$ and $K$ describing a query. ### Output For each query, print a single line containing one integer — the number of possible special menus modulo $2^{30}$. ### Constraints  $1 \le M \le 10^5$  $1 \le Q \le 10,000$  $1 \le L \le R \le M$  $1 \le K \le 10^9$ ### Example Input ``` 5 3 3 4 3 2 2 7 3 5 7 ``` ### Example Output ``` 8 0 3258 ``` ### Explanation The eight possible menus for the first morning (first query) are $(3, 4)$, $(4, 3)$, $(3, 3, 4)$, $(3, 4, 3)$, $(3, 4, 4)$, $(4, 3, 4)$, $(4, 3, 3)$, $(4, 4, 3)$.Author:  imanik 
Editorial  https://discuss.codechef.com/problems/MGICMENU 
Tags  cook108, divideandconq, imanik, inclusionexclusion, mobius, prefixsum, taran_1407 
Date Added:  12072019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions