#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll >
#define vvi vector<vi >
#define int long long int
int N, K, a, b;
int p[100000+100], qual[100000+10];
int mod = 786433, g = 10, w = 1000;
ll pw[(1<<18)],ans[786434];
ll powr(ll a, ll b, ll mod)
{
ll x = 1%mod;
a %= mod;
while(b)
{
if(b&1)
x = (x*a)%mod;
a = (a*a)%mod;
b >>= 1;
}
return x;
}
ll inv(ll a, ll mod)
{
return powr(a,mod-2,mod);
}
const int maxn = 1e6+10;
void mul_naive(vll& a, vll& b)
{
vll c(a.size()+b.size()-1);
for(int i = 0;i<a.size();i++)
for(int j = 0;j<b.size();j++)
c[i+j]+=a[i]*b[j];
a = c;
}
class NTT{
ll p,g,n,logn;
public:
NTT(ll P, ll G, ll LOGN)
{
p = P;
ll g1 = G;
logn = LOGN;
n = (1<<LOGN);
assert((p-1)%n == 0);
g = powr(g1,(p-1)>>logn,p);
}
int bitrevcopy(int i)
{
int ret = 0;
for(int j = 0;j<logn;j++)
if(i&(1<<j))
ret|=(1<<(logn-1-j));
return ret;
}
void fft(vll& a, bool invert)
{
ll mod = p;
for(int i = 0;i<n;i++)
{
int br = bitrevcopy(i);
if(i<br)
swap(a[i],a[br]);
}
for(int i = 1;i<=logn;i++)
{
ll mul = powr(g,1<<(logn-i),p);
if(invert)
mul = inv(mul,p);
int add = (1<<i);
for(int k = 0;k<n;k+=add)
{
ll w = 1;
ll lim = (add>>1);
for(int j = 0;j<lim;j++)
{
ll u = (w*a[k+j+lim])%p, v = a[k+j];
a[k+j] = u+v;
if(a[k+j]>=p)
a[k+j] -= p;
a[k+j+lim] = v-u;
if(a[k+j+lim]<0)
a[k+j+lim]+=p;
w = (w*mul)%p;
}
}
}
if(invert){
ll _inv = inv(n,p);
for(int i = 0;i<n;i++){
a[i] = (a[i]*_inv)%p;
}
}
}
};
void NTT_mul(vll& a, vll& B)
{
vll b = B;
int _sz = a.size()+b.size()-1;
int LOGN = 0;
while((1<<LOGN) < _sz)
LOGN++;
ll N = (1<<LOGN);
a.resize(N);
b.resize(N);
NTT fft1 = NTT(mod,g,LOGN);
fft1.fft(a,false);
fft1.fft(b,false);
for(int i = 0;i<N;i++){
a[i] = (a[i]*b[i])%mod;
}
fft1.fft(a,true);
a.resize(_sz);
}
void polymulmod(vll& a, vll& b, bool takemod, ll mod, bool give_a_fuck_about_precision)
{
int sa=a.size(),sb=b.size();
if(sa*1ll*sb <= 100000)
mul_naive(a,b);
else NTT_mul(a,b);
if(takemod)
for(int i = 0;i<a.size();i++)
a[i]%=mod;
}
vll solve(int l,int r)
{
if(l==r)
return {1-p[l],p[l]};
int m = (l+r)>>1;
vll v1 = solve(l,m);
vll v2 = solve(m+1,r);
polymulmod(v1,v2,1,mod,1);
return v1;
}
main()
{
// clock_t clk = clock();
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
scanf("%lld %lld",&N,&K);
for( int i=0 ; i < N ; i++ ){ scanf("%lld %lld %lld",&a,&b,&qual[i]); p[i]=a*inv(b,mod)%mod; }
vll a = solve(0, N-1);
int nn = K;
vll poly(K);
int c = 1;
for(int i=0;i<K;i++)
{
poly[i] = c*a[K-1-i];
c*=(-1);
}
poly.resize(mod);
NTT fft1 = NTT(mod,10,18);
vll poly1(mod);
c = 1;
for(int i=0;i<mod;i++)
{
poly1[i] = (poly[i]*c)%mod;
c = (c*10)%mod;
}
vll poly2(mod);
c = 1;
for(int i=0;i<mod;i++)
{
poly2[i] = (poly[i]*c)%mod;
c = (c*100)%mod;
}
fft1.fft(poly,false);
fft1.fft(poly1,false);
fft1.fft(poly2,false);
int root = 1000;
pw[0] = 1;
for(int i = 1; i < (1 << 18); i++)
pw[i] = (pw[i - 1] * root) % mod;
for(int i = 0; i < (1 << 18); i++) {
ans[pw[i]] = poly[i];
ans[pw[i] * 10 % mod] = poly1[i];
ans[pw[i] * 100 % mod] = poly2[i];
}
ll answer = 0;
for(int i=0;i<N;i++)
{if(p[i]==1)answer+=a[K]*1ll*qual[i];
else if(p[i] != 0)
{ ll x = (p[i]*1ll*inv(1-p[i],mod))%mod;
if(x<0)x += mod;
answer += (ans[x]*1ll*x%mod)*1ll*qual[i]%mod;
//cout<<(ans[x]*1ll*x%mod)<<endl;
}
answer %= mod;
//cout<<a[K]+mod<<endl;
}
answer = (answer+mod)%mod;
cout<<answer;
//cerr<<(float)(clock()-clk)/CLOCKS_PER_SEC;
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHZsbCB2ZWN0b3I8bGwgPgojZGVmaW5lIHZ2aSB2ZWN0b3I8dmkgPgojZGVmaW5lIGludCBsb25nIGxvbmcgaW50CiAKaW50IE4sIEssIGEsIGI7CmludCBwWzEwMDAwMCsxMDBdLCBxdWFsWzEwMDAwMCsxMF07CmludCBtb2QgPSA3ODY0MzMsIGcgPSAxMCwgdyA9IDEwMDA7CmxsIHB3WygxPDwxOCldLGFuc1s3ODY0MzRdOwogCmxsIHBvd3IobGwgYSwgbGwgYiwgbGwgbW9kKQp7CiAgICBsbCB4ID0gMSVtb2Q7CiAgICBhICU9IG1vZDsKICAgIHdoaWxlKGIpCiAgICB7CiAgICAgICAgaWYoYiYxKQogICAgICAgICAgICB4ID0gKHgqYSklbW9kOwogICAgICAgIGEgPSAoYSphKSVtb2Q7CiAgICAgICAgYiA+Pj0gMTsKICAgIH0KICAgIHJldHVybiB4Owp9CmxsIGludihsbCBhLCBsbCBtb2QpCnsKICAgIHJldHVybiBwb3dyKGEsbW9kLTIsbW9kKTsKfQogCmNvbnN0IGludCBtYXhuID0gMWU2KzEwOwogCnZvaWQgbXVsX25haXZlKHZsbCYgYSwgdmxsJiBiKQp7CiAgICB2bGwgYyhhLnNpemUoKStiLnNpemUoKS0xKTsKICAgIGZvcihpbnQgaSA9IDA7aTxhLnNpemUoKTtpKyspCiAgICAgICAgZm9yKGludCBqID0gMDtqPGIuc2l6ZSgpO2orKykKICAgICAgICAgICAgY1tpK2pdKz1hW2ldKmJbal07CiAgICBhID0gYzsgIAp9CiAKY2xhc3MgTlRUewogCiAgICBsbCBwLGcsbixsb2duOwpwdWJsaWM6CiAgICBOVFQobGwgUCwgbGwgRywgbGwgTE9HTikgICAgCiAgICB7CiAgICAgICAgcCA9IFA7CiAgICAgICAgbGwgZzEgPSBHOwogICAgICAgIGxvZ24gPSBMT0dOOwogICAgICAgIG4gPSAoMTw8TE9HTik7CiAgICAgICAgYXNzZXJ0KChwLTEpJW4gPT0gMCk7CiAgICAgICAgZyA9IHBvd3IoZzEsKHAtMSk+PmxvZ24scCk7CiAgICB9CiAKICAgIGludCBiaXRyZXZjb3B5KGludCBpKQogICAgewogICAgICAgIGludCByZXQgPSAwOwogICAgICAgIGZvcihpbnQgaiA9IDA7ajxsb2duO2orKykKICAgICAgICAgICAgaWYoaSYoMTw8aikpCiAgICAgICAgICAgICAgICByZXR8PSgxPDwobG9nbi0xLWopKTsKICAgICAgICByZXR1cm4gcmV0OwogICAgfQogICAgdm9pZCBmZnQodmxsJiBhLCBib29sIGludmVydCkKICAgIHsgICAKICAgICAgICBsbCBtb2QgPSBwOwogICAgICAgIGZvcihpbnQgaSA9IDA7aTxuO2krKykKICAgICAgICB7CiAgICAgICAgICAgIGludCBiciA9IGJpdHJldmNvcHkoaSk7CiAgICAgICAgICAgIGlmKGk8YnIpCiAgICAgICAgICAgICAgICBzd2FwKGFbaV0sYVticl0pOwogICAgICAgIH0KICAgICAgICBmb3IoaW50IGkgPSAxO2k8PWxvZ247aSsrKQogICAgICAgIHsKICAgICAgICAgICAgbGwgbXVsID0gcG93cihnLDE8PChsb2duLWkpLHApOwogICAgICAgICAgICBpZihpbnZlcnQpCiAgICAgICAgICAgICAgICBtdWwgPSBpbnYobXVsLHApOwogICAgICAgICAgICBpbnQgYWRkID0gKDE8PGkpOwogICAgICAgICAgICBmb3IoaW50IGsgPSAwO2s8bjtrKz1hZGQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGxsIHcgPSAxOwogICAgICAgICAgICAgICAgbGwgbGltID0gKGFkZD4+MSk7CiAgICAgICAgICAgICAgICBmb3IoaW50IGogPSAwO2o8bGltO2orKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBsbCB1ID0gKHcqYVtrK2orbGltXSklcCwgdiA9IGFbaytqXTsKICAgICAgICAgICAgICAgICAgICBhW2sral0gPSB1K3Y7CiAgICAgICAgICAgICAgICAgICAgaWYoYVtrK2pdPj1wKQogICAgICAgICAgICAgICAgICAgICAgICBhW2sral0gLT0gcDsKICAgICAgICAgICAgICAgICAgICBhW2sraitsaW1dID0gdi11OwogICAgICAgICAgICAgICAgICAgIGlmKGFbaytqK2xpbV08MCkKICAgICAgICAgICAgICAgICAgICAgICAgYVtrK2orbGltXSs9cDsKICAgICAgICAgICAgICAgICAgICB3ID0gKHcqbXVsKSVwOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmKGludmVydCl7CiAgICAgICAgICAgIGxsIF9pbnYgPSBpbnYobixwKTsKICAgICAgICAgICAgZm9yKGludCBpID0gMDtpPG47aSsrKXsKICAgICAgICAgICAgICAgIGFbaV0gPSAoYVtpXSpfaW52KSVwOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9Owp2b2lkIE5UVF9tdWwodmxsJiBhLCB2bGwmIEIpCnsKICAgIHZsbCBiID0gQjsKICAgIGludCBfc3ogPSBhLnNpemUoKStiLnNpemUoKS0xOwogICAgaW50IExPR04gPSAwOwogICAgd2hpbGUoKDE8PExPR04pIDwgX3N6KQogICAgICAgIExPR04rKzsKICAgIGxsIE4gPSAoMTw8TE9HTik7CiAgICBhLnJlc2l6ZShOKTsKICAgIGIucmVzaXplKE4pOwogICAgTlRUIGZmdDEgPSBOVFQobW9kLGcsTE9HTik7CiAgICBmZnQxLmZmdChhLGZhbHNlKTsKICAgIGZmdDEuZmZ0KGIsZmFsc2UpOwogICAgZm9yKGludCBpID0gMDtpPE47aSsrKXsKICAgICAgICBhW2ldID0gKGFbaV0qYltpXSklbW9kOwogICAgfQogICAgZmZ0MS5mZnQoYSx0cnVlKTsKICAgIGEucmVzaXplKF9zeik7Cn0gICAKIAp2b2lkIHBvbHltdWxtb2QodmxsJiBhLCB2bGwmIGIsIGJvb2wgdGFrZW1vZCwgbGwgbW9kLCBib29sIGdpdmVfYV9mdWNrX2Fib3V0X3ByZWNpc2lvbikKewogICAgaW50IHNhPWEuc2l6ZSgpLHNiPWIuc2l6ZSgpOwogCiAgICBpZihzYSoxbGwqc2IgPD0gMTAwMDAwKQogICAgICAgIG11bF9uYWl2ZShhLGIpOwogICAgZWxzZSBOVFRfbXVsKGEsYik7CiAgICBpZih0YWtlbW9kKQogICAgICAgIGZvcihpbnQgaSA9IDA7aTxhLnNpemUoKTtpKyspCiAgICAgICAgICAgIGFbaV0lPW1vZDsKfQp2bGwgc29sdmUoaW50IGwsaW50IHIpCnsKICAgIGlmKGw9PXIpCiAgICAgICAgcmV0dXJuIHsxLXBbbF0scFtsXX07CiAgICBpbnQgbSA9IChsK3IpPj4xOwogICAgdmxsIHYxID0gc29sdmUobCxtKTsKICAgIHZsbCB2MiA9IHNvbHZlKG0rMSxyKTsKICAgIHBvbHltdWxtb2QodjEsdjIsMSxtb2QsMSk7CiAgICByZXR1cm4gdjE7Cn0KbWFpbigpCnsKICAgIC8vIGNsb2NrX3QgY2xrID0gY2xvY2soKTsKICAgIC8vaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICAvL2Npbi50aWUoTlVMTCk7CiAgICBzY2FuZigiJWxsZCAlbGxkIiwmTiwmSyk7CiAgICBmb3IoIGludCBpPTAgOyBpIDwgTiA7IGkrKyApeyBzY2FuZigiJWxsZCAlbGxkICVsbGQiLCZhLCZiLCZxdWFsW2ldKTsgcFtpXT1hKmludihiLG1vZCklbW9kOyB9CiAgICB2bGwgYSA9IHNvbHZlKDAsIE4tMSk7CiAgICBpbnQgbm4gPSBLOwogIHZsbCBwb2x5KEspOwogIGludCBjID0gMTsKICBmb3IoaW50IGk9MDtpPEs7aSsrKQogIHsKICAgIHBvbHlbaV0gPSBjKmFbSy0xLWldOwogICAgYyo9KC0xKTsKICB9CiAgcG9seS5yZXNpemUobW9kKTsKICBOVFQgZmZ0MSA9IE5UVChtb2QsMTAsMTgpOwogICAgdmxsIHBvbHkxKG1vZCk7CiAgYyA9IDE7CiAgZm9yKGludCBpPTA7aTxtb2Q7aSsrKQogIHsKICAgICAgICBwb2x5MVtpXSA9IChwb2x5W2ldKmMpJW1vZDsKICAgICAgICBjID0gKGMqMTApJW1vZDsKICB9CiAgdmxsIHBvbHkyKG1vZCk7CiAgYyA9IDE7CiAgZm9yKGludCBpPTA7aTxtb2Q7aSsrKQogIHsKICAgICAgICBwb2x5MltpXSA9IChwb2x5W2ldKmMpJW1vZDsKICAgICAgICBjID0gKGMqMTAwKSVtb2Q7CiAgfQogIGZmdDEuZmZ0KHBvbHksZmFsc2UpOwogIGZmdDEuZmZ0KHBvbHkxLGZhbHNlKTsKICBmZnQxLmZmdChwb2x5MixmYWxzZSk7CiAgaW50IHJvb3QgPSAxMDAwOwogIHB3WzBdID0gMTsKICBmb3IoaW50IGkgPSAxOyBpIDwgKDEgPDwgMTgpOyBpKyspCiAgICAgICAgcHdbaV0gPSAocHdbaSAtIDFdICogcm9vdCkgJSBtb2Q7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgKDEgPDwgMTgpOyBpKyspIHsKICAgICAgICBhbnNbcHdbaV1dID0gcG9seVtpXTsKICAgICAgICBhbnNbcHdbaV0gKiAxMCAlIG1vZF0gPSBwb2x5MVtpXTsKICAgICAgICBhbnNbcHdbaV0gKiAxMDAgJSBtb2RdID0gcG9seTJbaV07CiAgICB9CiAgICBsbCBhbnN3ZXIgPSAwOwpmb3IoaW50IGk9MDtpPE47aSsrKQp7aWYocFtpXT09MSlhbnN3ZXIrPWFbS10qMWxsKnF1YWxbaV07CmVsc2UgaWYocFtpXSAhPSAwKQogIHsgICBsbCB4ID0gKHBbaV0qMWxsKmludigxLXBbaV0sbW9kKSklbW9kOwogICAgaWYoeDwwKXggKz0gbW9kOwogICAgYW5zd2VyICs9IChhbnNbeF0qMWxsKnglbW9kKSoxbGwqcXVhbFtpXSVtb2Q7CiAgICAvL2NvdXQ8PChhbnNbeF0qMWxsKnglbW9kKTw8ZW5kbDsKICB9CiAgYW5zd2VyICU9IG1vZDsKICAvL2NvdXQ8PGFbS10rbW9kPDxlbmRsOwp9CiAgICBhbnN3ZXIgPSAoYW5zd2VyK21vZCklbW9kOwogIGNvdXQ8PGFuc3dlcjsKICAvL2NlcnI8PChmbG9hdCkoY2xvY2soKS1jbGspL0NMT0NLU19QRVJfU0VDOwogICAgcmV0dXJuIDA7Cn0=