結果

問題 No.42 貯金箱の溜息
ユーザー chocoruskchocorusk
提出日時 2020-04-15 23:08:15
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 24 ms / 5,000 ms
コード長 25,147 bytes
コンパイル時間 1,170 ms
コンパイル使用メモリ 125,448 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-09 19:04:33
合計ジャッジ時間 1,843 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
6,812 KB
testcase_01 AC 24 ms
6,944 KB
testcase_02 AC 22 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+9;
const ll c5=666668756;
ll c[500][5]={{1, 499999973, 166669269, 833340870, 833340320}, {1, 499999973, 166669269, 833340870, 833340320}, {1, 499999973, 166669269, 833340870, 833340320}, {1, 499999973, 166669269, 833340870, 833340320}, {1, 499999973, 166669269, 833340870, 833340320}, {2, 666666693, 333336163, 666674481, 666673756}, {2, 666666693, 333336163, 666674481, 666673756}, {2, 666666693, 333336163, 666674481, 666673756}, {2, 666666693, 333336163, 666674481, 666673756}, {2, 666666693, 333336163, 666674481, 666673756}, {4, 666666755, 3070, 166674764, 500007192}, {4, 666666755, 3070, 166674764, 500007192}, {4, 666666755, 3070, 166674764, 500007192}, {4, 666666755, 3070, 166674764, 500007192}, {4, 666666755, 3070, 166674764, 500007192}, {6, 666666817, 666669986, 666675056, 333340628}, {6, 666666817, 666669986, 666675056, 333340628}, {6, 666666817, 666669986, 666675056, 333340628}, {6, 666666817, 666669986, 666675056, 333340628}, {6, 666666817, 666669986, 666675056, 333340628}, {9, 500000221, 833336915, 833342020, 166674064}, {9, 500000221, 833336915, 833342020, 166674064}, {9, 500000221, 833336915, 833342020, 166674064}, {9, 500000221, 833336915, 833342020, 166674064}, {9, 500000221, 833336915, 833342020, 166674064}, {12, 333333625, 3835, 8975, 7500}, {12, 333333625, 3835, 8975, 7500}, {12, 333333625, 3835, 8975, 7500}, {12, 333333625, 3835, 8975, 7500}, {12, 333333625, 3835, 8975, 7500}, {16, 371, 666670786, 833342620, 833340945}, {16, 371, 666670786, 833342620, 833340945}, {16, 371, 666670786, 833342620, 833340945}, {16, 371, 666670786, 833342620, 833340945}, {16, 371, 666670786, 833342620, 833340945}, {20, 666667126, 333337728, 666676256, 666674381}, {20, 666667126, 333337728, 666676256, 666674381}, {20, 666667126, 333337728, 666676256, 666674381}, {20, 666667126, 333337728, 666676256, 666674381}, {20, 666667126, 333337728, 666676256, 666674381}, {25, 166667214, 500004692, 166676564, 500007817}, {25, 166667214, 500004692, 166676564, 500007817}, {25, 166667214, 500004692, 166676564, 500007817}, {25, 166667214, 500004692, 166676564, 500007817}, {25, 166667214, 500004692, 166676564, 500007817}, {30, 666667311, 666671656, 666676881, 333341253}, {30, 666667311, 666671656, 666676881, 333341253}, {30, 666667311, 666671656, 666676881, 333341253}, {30, 666667311, 666671656, 666676881, 333341253}, {30, 666667311, 666671656, 666676881, 333341253}, {37, 500000749, 833338640, 833343870, 166674689}, {37, 500000749, 833338640, 833343870, 166674689}, {37, 500000749, 833338640, 833343870, 166674689}, {37, 500000749, 833338640, 833343870, 166674689}, {37, 500000749, 833338640, 833343870, 166674689}, {44, 333334187, 5615, 10850, 8125}, {44, 333334187, 5615, 10850, 8125}, {44, 333334187, 5615, 10850, 8125}, {44, 333334187, 5615, 10850, 8125}, {44, 333334187, 5615, 10850, 8125}, {53, 500000975, 166672619, 833344520, 833341570}, {53, 500000975, 166672619, 833344520, 833341570}, {53, 500000975, 166672619, 833344520, 833341570}, {53, 500000975, 166672619, 833344520, 833341570}, {53, 500000975, 166672619, 833344520, 833341570}, {62, 666667763, 333339623, 666678181, 666675006}, {62, 666667763, 333339623, 666678181, 666675006}, {62, 666667763, 333339623, 666678181, 666675006}, {62, 666667763, 333339623, 666678181, 666675006}, {62, 666667763, 333339623, 666678181, 666675006}, {73, 166667892, 500006647, 166678514, 500008442}, {73, 166667892, 500006647, 166678514, 500008442}, {73, 166667892, 500006647, 166678514, 500008442}, {73, 166667892, 500006647, 166678514, 500008442}, {73, 166667892, 500006647, 166678514, 500008442}, {84, 666668030, 666673671, 666678856, 333341878}, {84, 666668030, 666673671, 666678856, 333341878}, {84, 666668030, 666673671, 666678856, 333341878}, {84, 666668030, 666673671, 666678856, 333341878}, {84, 666668030, 666673671, 666678856, 333341878}, {97, 500001509, 833340715, 833345870, 166675314}, {97, 500001509, 833340715, 833345870, 166675314}, {97, 500001509, 833340715, 833345870, 166675314}, {97, 500001509, 833340715, 833345870, 166675314}, {97, 500001509, 833340715, 833345870, 166675314}, {110, 333334988, 7750, 12875, 8750}, {110, 333334988, 7750, 12875, 8750}, {110, 333334988, 7750, 12875, 8750}, {110, 333334988, 7750, 12875, 8750}, {110, 333334988, 7750, 12875, 8750}, {125, 500001817, 166674814, 833346570, 833342195}, {125, 500001817, 166674814, 833346570, 833342195}, {125, 500001817, 166674814, 833346570, 833342195}, {125, 500001817, 166674814, 833346570, 833342195}, {125, 500001817, 166674814, 833346570, 833342195}, {140, 666668646, 333341878, 666680256, 666675631}, {140, 666668646, 333341878, 666680256, 666675631}, {140, 666668646, 333341878, 666680256, 666675631}, {140, 666668646, 333341878, 666680256, 666675631}, {140, 666668646, 333341878, 666680256, 666675631}, {159, 666668825, 8960, 166680614, 500009067}, {159, 666668825, 8960, 166680614, 500009067}, {159, 666668825, 8960, 166680614, 500009067}, {159, 666668825, 8960, 166680614, 500009067}, {159, 666668825, 8960, 166680614, 500009067}, {178, 666669004, 666676051, 666680981, 333342503}, {178, 666669004, 666676051, 666680981, 333342503}, {178, 666669004, 666676051, 666680981, 333342503}, {178, 666669004, 666676051, 666680981, 333342503}, {178, 666669004, 666676051, 666680981, 333342503}, {201, 500002533, 833343160, 833348020, 166675939}, {201, 500002533, 833343160, 833348020, 166675939}, {201, 500002533, 833343160, 833348020, 166675939}, {201, 500002533, 833343160, 833348020, 166675939}, {201, 500002533, 833343160, 833348020, 166675939}, {224, 333336062, 10260, 15050, 9375}, {224, 333336062, 10260, 15050, 9375}, {224, 333336062, 10260, 15050, 9375}, {224, 333336062, 10260, 15050, 9375}, {224, 333336062, 10260, 15050, 9375}, {251, 2941, 666677396, 833348770, 833342820}, {251, 2941, 666677396, 833348770, 833342820}, {251, 2941, 666677396, 833348770, 833342820}, {251, 2941, 666677396, 833348770, 833342820}, {251, 2941, 666677396, 833348770, 833342820}, {278, 666669829, 333344523, 666682481, 666676256}, {278, 666669829, 333344523, 666682481, 666676256}, {278, 666669829, 333344523, 666682481, 666676256}, {278, 666669829, 333344523, 666682481, 666676256}, {278, 666669829, 333344523, 666682481, 666676256}, {309, 166670058, 500011677, 166682864, 500009692}, {309, 166670058, 500011677, 166682864, 500009692}, {309, 166670058, 500011677, 166682864, 500009692}, {309, 166670058, 500011677, 166682864, 500009692}, {309, 166670058, 500011677, 166682864, 500009692}, {340, 666670296, 666678831, 666683256, 333343128}, {340, 666670296, 666678831, 666683256, 333343128}, {340, 666670296, 666678831, 666683256, 333343128}, {340, 666670296, 666678831, 666683256, 333343128}, {340, 666670296, 666678831, 666683256, 333343128}, {375, 3875, 333346003, 833350320, 166676564}, {375, 3875, 333346003, 833350320, 166676564}, {375, 3875, 333346003, 833350320, 166676564}, {375, 3875, 333346003, 833350320, 166676564}, {375, 3875, 333346003, 833350320, 166676564}, {410, 333337463, 13175, 17375, 10000}, {410, 333337463, 13175, 17375, 10000}, {410, 333337463, 13175, 17375, 10000}, {410, 333337463, 13175, 17375, 10000}, {410, 333337463, 13175, 17375, 10000}, {451, 4401, 666680381, 833351120, 833343445}, {451, 4401, 666680381, 833351120, 833343445}, {451, 4401, 666680381, 833351120, 833343445}, {451, 4401, 666680381, 833351120, 833343445}, {451, 4401, 666680381, 833351120, 833343445}, {492, 666671348, 333347578, 666684856, 666676881}, {492, 666671348, 333347578, 666684856, 666676881}, {492, 666671348, 333347578, 666684856, 666676881}, {492, 666671348, 333347578, 666684856, 666676881}, {492, 666671348, 333347578, 666684856, 666676881}, {539, 666671645, 14800, 166685264, 500010317}, {539, 666671645, 14800, 166685264, 500010317}, {539, 666671645, 14800, 166685264, 500010317}, {539, 666671645, 14800, 166685264, 500010317}, {539, 666671645, 14800, 166685264, 500010317}, {586, 666671942, 666682031, 666685681, 333343753}, {586, 666671942, 666682031, 666685681, 333343753}, {586, 666671942, 666682031, 666685681, 333343753}, {586, 666671942, 666682031, 666685681, 333343753}, {586, 666671942, 666682031, 666685681, 333343753}, {639, 5589, 333349278, 833352770, 166677189}, {639, 5589, 333349278, 833352770, 166677189}, {639, 5589, 333349278, 833352770, 166677189}, {639, 5589, 333349278, 833352770, 166677189}, {639, 5589, 333349278, 833352770, 166677189}, {692, 333339245, 16525, 19850, 10625}, {692, 333339245, 16525, 19850, 10625}, {692, 333339245, 16525, 19850, 10625}, {692, 333339245, 16525, 19850, 10625}, {692, 333339245, 16525, 19850, 10625}, {751, 6251, 666683806, 833353620, 833344070}, {751, 6251, 666683806, 833353620, 833344070}, {751, 6251, 666683806, 833353620, 833344070}, {751, 6251, 666683806, 833353620, 833344070}, {751, 6251, 666683806, 833353620, 833344070}, {810, 666673266, 333351078, 666687381, 666677506}, {810, 666673266, 333351078, 666687381, 666677506}, {810, 666673266, 333351078, 666687381, 666677506}, {810, 666673266, 333351078, 666687381, 666677506}, {810, 666673266, 333351078, 666687381, 666677506}, {875, 666673631, 18375, 166687814, 500010942}, {875, 666673631, 18375, 166687814, 500010942}, {875, 666673631, 18375, 166687814, 500010942}, {875, 666673631, 18375, 166687814, 500010942}, {875, 666673631, 18375, 166687814, 500010942}, {940, 666673996, 666685681, 666688256, 333344378}, {940, 666673996, 666685681, 666688256, 333344378}, {940, 666673996, 666685681, 666688256, 333344378}, {940, 666673996, 666685681, 666688256, 333344378}, {940, 666673996, 666685681, 666688256, 333344378}, {1014, 500007721, 833353010, 833355370, 166677814}, {1014, 500007721, 833353010, 833355370, 166677814}, {1014, 500007721, 833353010, 833355370, 166677814}, {1014, 500007721, 833353010, 833355370, 166677814}, {1014, 500007721, 833353010, 833355370, 166677814}, {1088, 333341446, 20330, 22475, 11250}, {1088, 333341446, 20330, 22475, 11250}, {1088, 333341446, 20330, 22475, 11250}, {1088, 333341446, 20330, 22475, 11250}, {1088, 333341446, 20330, 22475, 11250}, {1171, 8531, 666687691, 833356270, 833344695}, {1171, 8531, 666687691, 833356270, 833344695}, {1171, 8531, 666687691, 833356270, 833344695}, {1171, 8531, 666687691, 833356270, 833344695}, {1171, 8531, 666687691, 833356270, 833344695}, {1254, 666675625, 333355043, 666690056, 666678131}, {1254, 666675625, 333355043, 666690056, 666678131}, {1254, 666675625, 333355043, 666690056, 666678131}, {1254, 666675625, 333355043, 666690056, 666678131}, {1254, 666675625, 333355043, 666690056, 666678131}, {1346, 166676070, 500022427, 166690514, 500011567}, {1346, 166676070, 500022427, 166690514, 500011567}, {1346, 166676070, 500022427, 166690514, 500011567}, {1346, 166676070, 500022427, 166690514, 500011567}, {1346, 166676070, 500022427, 166690514, 500011567}, {1438, 666676524, 666689811, 666690981, 333345003}, {1438, 666676524, 666689811, 666690981, 333345003}, {1438, 666676524, 666689811, 666690981, 333345003}, {1438, 666676524, 666689811, 666690981, 333345003}, {1438, 666676524, 666689811, 666690981, 333345003}, {1539, 10329, 333357218, 833358120, 166678439}, {1539, 10329, 333357218, 833358120, 166678439}, {1539, 10329, 333357218, 833358120, 166678439}, {1539, 10329, 333357218, 833358120, 166678439}, {1539, 10329, 333357218, 833358120, 166678439}, {1640, 333344143, 24625, 25250, 11875}, {1640, 333344143, 24625, 25250, 11875}, {1640, 333344143, 24625, 25250, 11875}, {1640, 333344143, 24625, 25250, 11875}, {1640, 333344143, 24625, 25250, 11875}, {1750, 500011317, 166692064, 833359070, 833345320}, {1750, 500011317, 166692064, 833359070, 833345320}, {1750, 500011317, 166692064, 833359070, 833345320}, {1750, 500011317, 166692064, 833359070, 833345320}, {1750, 500011317, 166692064, 833359070, 833345320}, {1860, 666678491, 333359503, 666692881, 666678756}, {1860, 666678491, 333359503, 666692881, 666678756}, {1860, 666678491, 333359503, 666692881, 666678756}, {1860, 666678491, 333359503, 666692881, 666678756}, {1860, 666678491, 333359503, 666692881, 666678756}, {1982, 166679026, 500026972, 166693364, 500012192}, {1982, 166679026, 500026972, 166693364, 500012192}, {1982, 166679026, 500026972, 166693364, 500012192}, {1982, 166679026, 500026972, 166693364, 500012192}, {1982, 166679026, 500026972, 166693364, 500012192}, {2104, 666679570, 666694441, 666693856, 333345628}, {2104, 666679570, 666694441, 666693856, 333345628}, {2104, 666679570, 666694441, 666693856, 333345628}, {2104, 666679570, 666694441, 666693856, 333345628}, {2104, 666679570, 666694441, 666693856, 333345628}, {2238, 500013475, 833361940, 833361020, 166679064}, {2238, 500013475, 833361940, 833361020, 166679064}, {2238, 500013475, 833361940, 833361020, 166679064}, {2238, 500013475, 833361940, 833361020, 166679064}, {2238, 500013475, 833361940, 833361020, 166679064}, {2372, 333347380, 29430, 28175, 12500}, {2372, 333347380, 29430, 28175, 12500}, {2372, 333347380, 29430, 28175, 12500}, {2372, 333347380, 29430, 28175, 12500}, {2372, 333347380, 29430, 28175, 12500}, {2518, 500014655, 166696959, 833362020, 833345945}, {2518, 500014655, 166696959, 833362020, 833345945}, {2518, 500014655, 166696959, 833362020, 833345945}, {2518, 500014655, 166696959, 833362020, 833345945}, {2518, 500014655, 166696959, 833362020, 833345945}, {2664, 666681930, 333364488, 666695856, 666679381}, {2664, 666681930, 333364488, 666695856, 666679381}, {2664, 666681930, 333364488, 666695856, 666679381}, {2664, 666681930, 333364488, 666695856, 666679381}, {2664, 666681930, 333364488, 666695856, 666679381}, {2822, 166682566, 500032047, 166696364, 500012817}, {2822, 166682566, 500032047, 166696364, 500012817}, {2822, 166682566, 500032047, 166696364, 500012817}, {2822, 166682566, 500032047, 166696364, 500012817}, {2822, 166682566, 500032047, 166696364, 500012817}, {2980, 666683211, 666699606, 666696881, 333346253}, {2980, 666683211, 666699606, 666696881, 333346253}, {2980, 666683211, 666699606, 666696881, 333346253}, {2980, 666683211, 666699606, 666696881, 333346253}, {2980, 666683211, 666699606, 666696881, 333346253}, {3150, 500017217, 833367195, 833364070, 166679689}, {3150, 500017217, 833367195, 833364070, 166679689}, {3150, 500017217, 833367195, 833364070, 166679689}, {3150, 500017217, 833367195, 833364070, 166679689}, {3150, 500017217, 833367195, 833364070, 166679689}, {3320, 333351223, 34775, 31250, 13125}, {3320, 333351223, 34775, 31250, 13125}, {3320, 333351223, 34775, 31250, 13125}, {3320, 333351223, 34775, 31250, 13125}, {3320, 333351223, 34775, 31250, 13125}, {3506, 18601, 666702401, 833365120, 833346570}, {3506, 18601, 666702401, 833365120, 833346570}, {3506, 18601, 666702401, 833365120, 833346570}, {3506, 18601, 666702401, 833365120, 833346570}, {3506, 18601, 666702401, 833365120, 833346570}, {3692, 666685988, 333370018, 666698981, 666680006}, {3692, 666685988, 333370018, 666698981, 666680006}, {3692, 666685988, 333370018, 666698981, 666680006}, {3692, 666685988, 333370018, 666698981, 666680006}, {3692, 666685988, 333370018, 666698981, 666680006}, {3894, 166686738, 500037672, 166699514, 500013442}, {3894, 166686738, 500037672, 166699514, 500013442}, {3894, 166686738, 500037672, 166699514, 500013442}, {3894, 166686738, 500037672, 166699514, 500013442}, {3894, 166686738, 500037672, 166699514, 500013442}, {4096, 666687497, 666705326, 666700056, 333346878}, {4096, 666687497, 666705326, 666700056, 333346878}, {4096, 666687497, 666705326, 666700056, 333346878}, {4096, 666687497, 666705326, 666700056, 333346878}, {4096, 666687497, 666705326, 666700056, 333346878}, {4314, 21619, 333373008, 833367270, 166680314}, {4314, 21619, 333373008, 833367270, 166680314}, {4314, 21619, 333373008, 833367270, 166680314}, {4314, 21619, 333373008, 833367270, 166680314}, {4314, 21619, 333373008, 833367270, 166680314}, {4532, 333355750, 40690, 34475, 13750}, {4532, 333355750, 40690, 34475, 13750}, {4532, 333355750, 40690, 34475, 13750}, {4532, 333355750, 40690, 34475, 13750}, {4532, 333355750, 40690, 34475, 13750}, {4766, 500023253, 166708409, 833368370, 833347195}, {4766, 500023253, 166708409, 833368370, 833347195}, {4766, 500023253, 166708409, 833368370, 833347195}, {4766, 500023253, 166708409, 833368370, 833347195}, {4766, 500023253, 166708409, 833368370, 833347195}, {5000, 666690756, 333376128, 666702256, 666680631}, {5000, 666690756, 333376128, 666702256, 666680631}, {5000, 666690756, 333376128, 666702256, 666680631}, {5000, 666690756, 333376128, 666702256, 666680631}, {5000, 666690756, 333376128, 666702256, 666680631}, {5250, 666691631, 43875, 166702814, 500014067}, {5250, 666691631, 43875, 166702814, 500014067}, {5250, 666691631, 43875, 166702814, 500014067}, {5250, 666691631, 43875, 166702814, 500014067}, {5250, 666691631, 43875, 166702814, 500014067}, {5500, 666692506, 666711631, 666703381, 333347503}, {5500, 666692506, 666711631, 666703381, 333347503}, {5500, 666692506, 666711631, 666703381, 333347503}, {5500, 666692506, 666711631, 666703381, 333347503}, {5500, 666692506, 666711631, 666703381, 333347503}, {5770, 26755, 333379413, 833370620, 166680939}, {5770, 26755, 333379413, 833370620, 166680939}, {5770, 26755, 333379413, 833370620, 166680939}, {5770, 26755, 333379413, 833370620, 166680939}, {5770, 26755, 333379413, 833370620, 166680939}, {6040, 333361013, 47195, 37850, 14375}, {6040, 333361013, 47195, 37850, 14375}, {6040, 333361013, 47195, 37850, 14375}, {6040, 333361013, 47195, 37850, 14375}, {6040, 333361013, 47195, 37850, 14375}, {6330, 28645, 666715021, 833371770, 833347820}, {6330, 28645, 666715021, 833371770, 833347820}, {6330, 28645, 666715021, 833371770, 833347820}, {6330, 28645, 666715021, 833371770, 833347820}, {6330, 28645, 666715021, 833371770, 833347820}, {6620, 666696286, 333382838, 666705681, 666681256}, {6620, 666696286, 333382838, 666705681, 666681256}, {6620, 666696286, 333382838, 666705681, 666681256}, {6620, 666696286, 333382838, 666705681, 666681256}, {6620, 666696286, 333382838, 666705681, 666681256}, {6930, 666697301, 50690, 166706264, 500014692}, {6930, 666697301, 50690, 166706264, 500014692}, {6930, 666697301, 50690, 166706264, 500014692}, {6930, 666697301, 50690, 166706264, 500014692}, {6930, 666697301, 50690, 166706264, 500014692}, {7240, 666698316, 666718551, 666706856, 333348128}, {7240, 666698316, 666718551, 666706856, 333348128}, {7240, 666698316, 666718551, 666706856, 333348128}, {7240, 666698316, 666718551, 666706856, 333348128}, {7240, 666698316, 666718551, 666706856, 333348128}, {7570, 32705, 333386438, 833374120, 166681564}, {7570, 32705, 333386438, 833374120, 166681564}, {7570, 32705, 333386438, 833374120, 166681564}, {7570, 32705, 333386438, 833374120, 166681564}, {7570, 32705, 333386438, 833374120, 166681564}, {7900, 333367103, 54325, 41375, 15000}, {7900, 333367103, 54325, 41375, 15000}, {7900, 333367103, 54325, 41375, 15000}, {7900, 333367103, 54325, 41375, 15000}, {7900, 333367103, 54325, 41375, 15000}, {8250, 34875, 666722256, 833375320, 833348445}, {8250, 34875, 666722256, 833375320, 833348445}, {8250, 34875, 666722256, 833375320, 833348445}, {8250, 34875, 666722256, 833375320, 833348445}, {8250, 34875, 666722256, 833375320, 833348445}, {8600, 666702656, 333390178, 666709256, 666681881}, {8600, 666702656, 333390178, 666709256, 666681881}, {8600, 666702656, 333390178, 666709256, 666681881}, {8600, 666702656, 333390178, 666709256, 666681881}, {8600, 666702656, 333390178, 666709256, 666681881}, {8975, 166703814, 500058142, 166709864, 500015317}, {8975, 166703814, 500058142, 166709864, 500015317}, {8975, 166703814, 500058142, 166709864, 500015317}, {8975, 166703814, 500058142, 166709864, 500015317}, {8975, 166703814, 500058142, 166709864, 500015317}, {9350, 666704981, 666726106, 666710481, 333348753}, {9350, 666704981, 666726106, 666710481, 333348753}, {9350, 666704981, 666726106, 666710481, 333348753}, {9350, 666704981, 666726106, 666710481, 333348753}, {9350, 666704981, 666726106, 666710481, 333348753}, {9750, 39525, 333394103, 833377770, 166682189}, {9750, 39525, 333394103, 833377770, 166682189}, {9750, 39525, 333394103, 833377770, 166682189}, {9750, 39525, 333394103, 833377770, 166682189}, {9750, 39525, 333394103, 833377770, 166682189}, {10150, 333374078, 62100, 45050, 15625}, {10150, 333374078, 62100, 45050, 15625}, {10150, 333374078, 62100, 45050, 15625}, {10150, 333374078, 62100, 45050, 15625}, {10150, 333374078, 62100, 45050, 15625}, {10575, 500042017, 166730139, 833379020, 833349070}, {10575, 500042017, 166730139, 833379020, 833349070}, {10575, 500042017, 166730139, 833379020, 833349070}, {10575, 500042017, 166730139, 833379020, 833349070}, {10575, 500042017, 166730139, 833379020, 833349070}, {11000, 666709956, 333398178, 666712981, 666682506}, {11000, 666709956, 333398178, 666712981, 666682506}, {11000, 666709956, 333398178, 666712981, 666682506}, {11000, 666709956, 333398178, 666712981, 666682506}, {11000, 666709956, 333398178, 666712981, 666682506}, {11450, 666711281, 66250, 166713614, 500015942}, {11450, 666711281, 66250, 166713614, 500015942}, {11450, 666711281, 66250, 166713614, 500015942}, {11450, 666711281, 66250, 166713614, 500015942}, {11450, 666711281, 66250, 166713614, 500015942}, {11900, 666712606, 666734331, 666714256, 333349378}, {11900, 666712606, 666734331, 666714256, 333349378}, {11900, 666712606, 666734331, 666714256, 333349378}, {11900, 666712606, 666734331, 666714256, 333349378}, {11900, 666712606, 666734331, 666714256, 333349378}, {12375, 500047317, 833402445, 833381570, 166682814}, {12375, 500047317, 833402445, 833381570, 166682814}, {12375, 500047317, 833402445, 833381570, 166682814}, {12375, 500047317, 833402445, 833381570, 166682814}, {12375, 500047317, 833402445, 833381570, 166682814}, {12850, 333382028, 70550, 48875, 16250}, {12850, 333382028, 70550, 48875, 16250}, {12850, 333382028, 70550, 48875, 16250}, {12850, 333382028, 70550, 48875, 16250}, {12850, 333382028, 70550, 48875, 16250}, {13355, 500050137, 166738704, 833382870, 833349695}, {13355, 500050137, 166738704, 833382870, 833349695}, {13355, 500050137, 166738704, 833382870, 833349695}, {13355, 500050137, 166738704, 833382870, 833349695}, {13355, 500050137, 166738704, 833382870, 833349695}, {13860, 666718246, 333406858, 666716856, 666683131}, {13860, 666718246, 333406858, 666716856, 666683131}, {13860, 666718246, 333406858, 666716856, 666683131}, {13860, 666718246, 333406858, 666716856, 666683131}, {13860, 666718246, 333406858, 666716856, 666683131}, {14395, 166719744, 500075052, 166717514, 500016567}, {14395, 166719744, 500075052, 166717514, 500016567}, {14395, 166719744, 500075052, 166717514, 500016567}, {14395, 166719744, 500075052, 166717514, 500016567}, {14395, 166719744, 500075052, 166717514, 500016567}, {14930, 666721251, 666743246, 666718181, 333350003}, {14930, 666721251, 666743246, 666718181, 333350003}, {14930, 666721251, 666743246, 666718181, 333350003}, {14930, 666721251, 666743246, 666718181, 333350003}, {14930, 666721251, 666743246, 666718181, 333350003}, {15495, 500056147, 833411480, 833385520, 166683439}, {15495, 500056147, 833411480, 833385520, 166683439}, {15495, 500056147, 833411480, 833385520, 166683439}, {15495, 500056147, 833411480, 833385520, 166683439}, {15495, 500056147, 833411480, 833385520, 166683439}, {16060, 333391043, 79705, 52850, 16875}, {16060, 333391043, 79705, 52850, 16875}, {16060, 333391043, 79705, 52850, 16875}, {16060, 333391043, 79705, 52850, 16875}, {16060, 333391043, 79705, 52850, 16875}, {16655, 500059337, 166747979, 833386870, 833350320}, {16655, 500059337, 166747979, 833386870, 833350320}, {16655, 500059337, 166747979, 833386870, 833350320}, {16655, 500059337, 166747979, 833386870, 833350320}, {16655, 500059337, 166747979, 833386870, 833350320}, {17250, 666727631, 333416253, 666720881, 666683756}, {17250, 666727631, 333416253, 666720881, 666683756}, {17250, 666727631, 333416253, 666720881, 666683756}, {17250, 666727631, 333416253, 666720881, 666683756}, {17250, 666727631, 333416253, 666720881, 666683756}, {17875, 166729314, 500084567, 166721564, 500017192}, {17875, 166729314, 500084567, 166721564, 500017192}, {17875, 166729314, 500084567, 166721564, 500017192}, {17875, 166729314, 500084567, 166721564, 500017192}, {17875, 166729314, 500084567, 166721564, 500017192}, {18500, 666731006, 666752881, 666722256, 333350628}, {18500, 666731006, 666752881, 666722256, 333350628}, {18500, 666731006, 666752881, 666722256, 333350628}, {18500, 666731006, 666752881, 666722256, 333350628}, {18500, 666731006, 666752881, 666722256, 333350628}};
int main()
{
	int t; cin>>t;
    while(t--){
        ll m; cin>>m;
        ll p=1, x=m/500%MOD, ans=0;
        for(int i=0; i<5; i++){
            (ans+=p*c[m%500][i])%=MOD;
            (p*=x)%=MOD;
        }
        cout<<(ans+c5*p)%MOD<<endl;
    }
	return 0;
}
0