there city park represent tree n attraction vertex n 1 rail edge the ith attraction happiness value a_ieach rail color it black t_i 0 white t_i 1 black train operate black rail track white train operate white rail track if previously black train want ride white train previously white train want ride black train need use 1 ticketthe path tour simple path visit attraction you need ticket time board train you k ticket mean switch train type k time in particular need ticket path consist rail colordefine fu v sum happiness value attraction tour u v simple path start uth attraction end vth attraction find sum fuv valid tour u v 1 leq u leq v leq n need k ticket modulo 109 7