{"raw_statement":[{"iden":"statement","content":"Altanie is a very large and strange country in Mars. People of Mars ages a lot. Some of them live for thousands of centuries!\n\nYour old friend Foki \"The president of the Martian United States of Altanie\" is the oldest man on Mars. He's very old no one knows how old he is! Foki loves children, so, he had (0 < K ≤ 106) children! \n\nThe government in Altanie decided to send a team of athletes to Venus. To participate in (0 < N ≤ 103) different game in the Galactic Olympics. So Foki told them to send his children instead! \n\nFoki is in a big problem. How can he decide whom of his children is going to participate in which game, at the same time his children must participate in all the games and every one of his children get to participate in at least one game?\n\nNote that in a certain arrangement, each one of Foki's children can participate in multiple games in the Olympics, but each game must be arranged to exactly one player.\n\nYour job is to help Foki and answer his question: in how many way can he arrange his children to the games in Venus Olympics while satisfying the previous two conditions.\n\nThe first line of the input contains T the number of the test cases. Each test is represented with two integers on a single line. ( 0 < N ≤ 103 ) the number of the games in the Olympics, ( 0 < K ≤ 106 ) the number of Foki's children. \n\nFor each test case print one line contains the answer to Foki's question. Since the answer is very large. Print the answer modulo 109 + 7\n\n"},{"iden":"input","content":"The first line of the input contains T the number of the test cases. Each test is represented with two integers on a single line. ( 0 < N ≤ 103 ) the number of the games in the Olympics, ( 0 < K ≤ 106 ) the number of Foki's children. "},{"iden":"output","content":"For each test case print one line contains the answer to Foki's question. Since the answer is very large. Print the answer modulo 109 + 7"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ N \\in \\mathbb{Z} $ be the number of games, and $ K \\in \\mathbb{Z} $ be the number of children.\n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{unknown} $ (implied by input format)  \n2. $ 1 \\le N \\le 10^3 $  \n3. $ 1 \\le K \\le 10^6 $  \n\n**Objective**  \nFor each test case, compute the number of surjective functions from the set of $ K $ children to the set of $ N $ games, where each game is assigned exactly one child, and every child participates in at least one game.  \n\nThis is equivalent to counting the number of ways to assign each of the $ N $ games to one of the $ K $ children such that all $ K $ children are used at least once.  \n\nHowever, since each game must be assigned to *exactly one* child, and children can be assigned to *multiple* games, we are assigning $ N $ distinct games to $ K $ children with the constraint that **every child is assigned to at least one game**.  \n\nThis is only possible if $ K \\le N $, and the number of such assignments is:  \n$$\n\\sum_{i=0}^{K} (-1)^i \\binom{K}{i} (K - i)^N\n$$  \nwhich is the number of **surjective functions** from a set of size $ N $ (games) to a set of size $ K $ (children), i.e., the number of ways to assign $ N $ distinct games to $ K $ distinct children such that no child is left out.\n\nBut note: the problem says \"**each game must be arranged to exactly one player**\" and \"**every one of his children get to participate in at least one game**\".  \n\nSo:  \n- Each game → one child (function from games to children)  \n- Every child → at least one game (surjective)  \n\nThus, the number of valid assignments is the number of **surjective functions** from the set of $ N $ games to the set of $ K $ children:  \n\n$$\n\\boxed{ \\sum_{i=0}^{K} (-1)^i \\binom{K}{i} (K - i)^N }\n$$\n\nBut note: this is only nonzero when $ K \\le N $. If $ K > N $, it's impossible to assign $ N $ games to $ K $ children with each child getting at least one game → answer is 0.\n\n**Final Objective**  \nFor each test case, compute:  \n$$\n\\text{ans} = \n\\begin{cases} \n\\displaystyle \\sum_{i=0}^{K} (-1)^i \\binom{K}{i} (K - i)^N \\mod (10^9 + 7) & \\text{if } K \\le N \\\\\n0 & \\text{if } K > N \n\\end{cases}\n$$","simple_statement":"You are given T test cases. For each test case, you are given two integers N (number of games) and K (number of children).  \n\nEach game must be assigned to exactly one child.  \nEach child must be assigned to at least one game.  \nA child can be assigned to multiple games.  \n\nCount the number of ways to assign the N games to K children such that no child is left out.  \n\nAnswer modulo 10^9 + 7.","has_page_source":false}