P20539 [HackerEarth] Problem :
普及
题目描述

Problem :

Baba wants to kill Guruji. He has a master plan but Guruji is prepared for him.

Baba released a bacterial concentration of 1 unit in Guruji's underground water source on Day 0. The concentration of bacteria becomes x times the concentration day before. But,Guruji's powder kills y units of bacteria each day, starting from Day 1.

Guruji needs your help to estimate the concentration of bacteria on the N th day.

Note : Large Input/Output Data. Use fast I/O.

Input :

First line consists of 2 space separated integers x and y. The next line consists of a single integer Q, denoting the number of queries Guruji has for you. The next Q lines are such that each line consists of a single integer N.

Output :

For each query of Guruji, print the number of bacteria present on the N th day on a new line. Since the answer can be really huge, print the answer modulo 1000000007 (10^9 + 7) .

Constraints :

2 ≤ x ≤ 100

0 ≤ y ≤ (x-2)

1 ≤ Q ≤ 10^6

1 ≤ N ≤ 10^6

Problem Setter : Sayan

Problem Tester : Sandeep , Himanshu

(By IIT Kgp HackerEarth Programming Club)

SAMPLE INPUT
5 3
3
1
3
2

SAMPLE OUTPUT
2
32
7

输入格式

见题面

输出格式

见题面

样例输入
12 1 731 5675 7426 262 1725 8945 8125 1918 3230 4774 8806 98 1100 5794 7985 2546 4757 7690 3583 3566 2412 5189 4992 838 3678 7516 8695 3731 1013 656 8750 2101 4060 8256 5642 8749 3396 6171 4815 860 1319 9282 5623 5386 6460 4354 9231 9595 651 4945 691 32 1265 1974 5227 7562 6565 3822 918 7636 9419 2941 5318 2626 8441 5458 7131 9844 6105 9854 7893 5055 399 6101 116 4894 9115 3494 9203 5861 6737 8104 3237 3319 7303 869 3677 8152 3390 1084 7060 1125 581 6289 6871 450 938 5048 1247 6452 2098 1442 1206 1153 3180 8679 3526 2021 2593 821 6036 1735 1102 4487 5309 7210 757 8297 5423 8328 4113 4219 555 2092 2393 7973 3626 6959 7734 2203 654 4310 2360 3408 2762 7785 3030 6175 1476 2999 1925 503 9258 8520 6956 7127 9843 6627 8901 11 6936 8562 2741 8326 2611 5107 4256 753 9958 1680 1831 6738 3022 1984 2147 2016 3034 7263 5671 1318 6295 6892 5345 6662 5326 6738 929 8160 320 6554 9437 19 4384 8542 1172 7603 7746 3728 1538 1180 4403 3356 2419 8646 409 876 4379 9017 6652 1115 1941 5315 1926 60 891 2744 5927 1660 6470 7129 6299 4805 4342 3352 3632 4404 1956 3658 9330 2653 1110 1294 729 5485 5507 2558 1575 7985 7320 9956 5178 85 7802 8479 5625 2767 7036 7685 8605 6702 2147 986 5117 7565 4328 3298 4702 8732 7230 8276 2970 2177 1350 2465 1329 8010 4991 4979 5198 3142 9665 8632 9868 1365 1564 2993 9656 2574 6524 6982 3368 32 7184 1325 4652 5546 8843 6939 7316 8862 1482 7881 3123 7123 6600 8778 3827 1787 4351 2589 6664 6245 8847 5406 3369 9668 6660 6754 5132 9871 835 4387 9921 1801 7620 9912 8867 596 6071 2376 2586 3042 9856 8000 4788 6221 2709 884 7237 7960 490 3939 204 2789 9338 6126 3561 2312 7177 6761 940 651 184 1907 2127 5844 153 7619 2263 1860 1235 8739 4087 4273 7080 2642 741 2726 9797 453 273 5817 4361 525 6131 3870 6042 431 9716 9674 6789 7423 2048 6507 6292 2574 779 9670 1061 5495 5426 2384 9992 3412 5091 9233 5769 6614 5375 1030 1183 7413 5806 9398 3108 2949 6996 3416 903 6217 803 275 1518 556 1201 6325 9615 8750 6364 1080 7281 1995 3947 4210 9502 7571 262 3820 892 5973 8089 2821 1693 2717 9172 6423 691 9216 9735 5419 1832 7941 2717 153 5277 5383 4454 7363 6577 5512 762 3250 5333 1912 2266 6048 3965 3415 1193 5912 5305 343 1595 5387 4885 8341 7100 2133 8958 7513 756 9471 5478 2779 5514 6262 7098 233 6711 6939 3410 8967 1085 9644 9624 1286 9832 1140 8013 1400 1939 9839 4216 5059 9149 1616 5824 52 6013 7142 2109 5126 8084 764 5530 7234 1715 7536 1133 3609 5117 743 4009 9009 5838 4639 6916 9724 4939 8324 549 5775 716 6375 7953 1793 88 4460 1078 9107 4800 9587 2231 2287 7518 1786 6105 3299 5231 9361 3885 4192 5663 4526 2080 3790 3220 1825 9087 9779 9198 4810 9215 9044 9901 8282 1963 7930 7059 2472 5951 3321 8203 4053 997 1101 939 8929 5598 3990 5206 6336 6980 9765 2117 6871 1757 791 8359 6780 5906 3106 6454 2333 385 7502 7100 1999 4048 7190 486 4266 8947 1535 8968 4338 7967 5544 5233 7578 1136 6114 6641 5044 9928 5521 4328 1964 4217 4676 3312 1526 9493 4306 2173 3765 4708 8470 8548 8717 9894 9004 1338 9595 5609 5308 1231 7924 589 8071 8906 2555 1350 7503 2535 2983 1826 6828 2687 4052 9372 2204 4294 4537 4320 9851 2362 4810 6031 4755 2938 542 7542 9141 2198 2740 218 5529 8822 9810 8662 1939 2702 7678 841 1478 48 5168 9658 925 8130 2983 333 2856 9985 6267 2746 3620 3574 8468 2476 5726 5896 4329 151 3545 5122 3579 5790 1341 6967 371 1572 8883 8979 7897 5713 687 4964 295 2759 2461 4905 4205 22 8207 3226 3622 9485 6901 2904 6107 897 1774 7205 3382 8771 1103 6551 3130 4077 5682 8889 3041 2125 9744 5107 3766 6342 497 3836 740 1123 7955 3341 3230 1789 9786 6551 2721 4367 87 3528 1927 6887 1548 3578 221 6800 1503 5164 6935
样例输出
269871385 164551775 759017191 251903870 252754982 784008845 962702628 760099456 420950080 905273010 899826709 802077697 105294504 737853293 327886746 440424195 274812860 780711348 311460931 326353443 233545750 665772447 427460107 808347899 941251209 777082195 28583403 26391368 245416914 320045316 793857321 302184605 246308815 367324291 262486929 209348531 856276097 145959106 386990126 383241628 327886746 184271523 731175627 650192054 478893782 298982937 492637847 951768224 142106019 802077697 929732891 870073826 342267527 938423299 752984423 342853065 830214476 315390646 841358887 419873673 892424031 563737771 561881525 116444396 134315445 161207527 595286748 663164751 360885410 477078679 991386766 626748169 23352881 635464501 506467756 456586853 542642403 12078450 732191560 934149365 784008845 693532134 899817715 571559297 254071502 35703366 190648430 158934697 342267527 140024713 205488388 626268145 245811089 512378867 369509876 785626877